Forem: Bill Morrisson

On the Nature and Limits of Computational Complexity

Bill Morrisson — Wed, 11 Mar 2020 15:13:12 +0000

Solving problems is the bread and butter of computing and mathematics in general. Without that urge of solving problems our world will not exist in our present form. Going to work and/or school, cooking some food, going on vacations, etc. are still forms of problems even if you don't take notice of that 🙂.

In this article I try to talk in a way such that even a non-computer science inclined person can understand.
I talk about the deepest unanswered question in computer science and maybe in all of mathematics; A problem called P vs NP and I want to talk about how ideas from computing show up in the everyday world around us and how very difficult problems like protein folding(process/method used for curing cancer) that seem so different from cross-word puzzles share a common core difficulty that turns out to be a lot like Sudoku.

Basically all of them are one and the same problem.

In 2000 the Clay institute offered $1 million each for the solutions to 7 key problems in math; The Millennium Prize Problems.

These are profound and difficult problems and for most of them it takes a lot of specialized knowledge to even understand the question. Of the 7 problems P vs NP was both the most recently conceived in 1971 and by far the easiest one to understand and explain(kind of why I maybe decided to write for this particular problem 🙂)

In March 2010 the Clay institute awarded the first of its 7 prizes to Grigori Perelman for the solution to the Poincare Conjecture.
So what is the P vs NP question actually?

Some history…

Back in the 70s computer scientists were busily figuring out how to program their retro cabinet-sized computers to solve all the world’s problems. Sometimes the first program that anyone could think of for a particular problem will be unworkably slow but then overtime we("we" here as in the computer science community as a whole) will come up with clever ways to make it faster. That happened for some problems, for others nobody was able to come up with faster programs.

To get a handle on the situation we started sorting the problems into classes; based on how fast a program could solve them. For problems like multiplication they had really fast programs and for others like playing absolutely perfect chess they figured out that there was just no fast program but for some in between they weren’t sure whether there was a fast way to do it so they kept trying…

This is where P vs NP come in. Skipping a ton of details P is a class that basically include all the problems that can be solved by a reasonably fast program like multiplication or putting names in alphabetical order and then around and including P we sort of discovered a class called NP; that’s all the problems where if you are given a correct solution you can at least check it in a reasonable amount of time.
NP was a new and total maddening class as it contained a lot of important problems like vehicle routing, scheduling timetables, problems in circuit design and databases. Often we might find out that an NP problem was actually part of P and we will have our fast program but for a lot of them that didn't seem to be happening. So we started to wonder whether everything in NP will turn out to be in P(P = NP) or if there were some problems that were truly harder than the ones in P(P != NP); That's the P vs NP question.
If all the NP problems are really in P then a lot of important problems we've been struggling with are going to turn out to be easy for computers to solve; problems connected to biology and curing cancer, problems in business and economics, we'll have a lot of miracle answers almost overnight but sadly the security used for our online banking and other financial transactions will be easy to crack as it's based on NP problems.

Let's think about these problems as puzzles. I like puzzles as what makes a puzzle a puzzle is that it's a problem where you can give away the answer, and that's what NP means.
For example with Sudoku; Sudoku puzzles can take a long time to solve but if I give you a solved grid, checking it for mistakes is pretty quick .
Outside of NP are problems where it's hard to even check whether the answer is wrong or right.
For example what's the best move to make in this chess game?

I could tell you the answer but how would you know whether I am right? You wouldn't because finding out requires a calculation so enormous that there's a pretty good argument we'll never be able to build a computer that could do it. To me that's not a good puzzle because it's practically impossible to know whether you've solved it.

On the other side are all the reasonable and solvable problems in P. These are clearly also in NP because one way to check an answer is to go through the process of solving it yourself. Like if for example I tell you that the answer to 72x4 is 288, how would you know whether I am right? You would probably multiply those numbers yourself to check because it's fast to do it.
But Sudoku is "different", or at least, we think it is. It seems like solving a Sudoku grid is a lot harder than checking a solution, but in fact nobody has been able to prove it yet. As far as we know, there could be a clever way of playing Sudoku, much much faster.

So that's the question; Does being able to quickly recognize correct answers means there's also a quick way to find them? Another way of putting is asking Is P = NP or P != NP(Is P equal to NP or not equal NP)?
Nobody knows for sure, but either way, figuring out exactly how this works would teach us something important about the nature of computation.

It gets weirder from here but first: three important details.

1. Levels of growing difficulty

You might be thinking: hey, Sudoku is tough and all but it's not that hard. What's the big deal about it? Well we're really talking about how the difficulty scales up as you make the problem bigger and bigger.
Like how much harder is a 100x100 Sudoku grid than a standard 9x9 grid?

We've been making computers exponentially faster as time went by, so, for problems that don't get exponentially harder as they get bigger, all we have to do is wait for computers to get more powerful and then, even huge versions of those problems will be easy to solve by a computer.
Multiplication for example; even with huge or enormous numbers multiplication problems are pretty easy for computers. As the number gets bigger, multiplying them doesn't just get any harder very fast.
These days, the phone in your pocket is what would have been referred to in the 1970's as a "supercomputer".(On a tangent here; remember they used those computers in the 1970's to send a man to the moon but now the "supercomputer" in your pocket just sits there and/or helps you to like funny pictures or get laid, but that's a story for another time 😬)

You'd have to make up truly huge multiplication problems to stand up to all the computational power we've got now.
Lots of familiar puzzles like Rubik's cube and mazes are in the same camp; hard for humans, but easy work for computers.

And then there's Sudoku. Computers can usually solve a 9x9 grid in a few milliseconds even though humans find them challenging but as you make the grid bigger and bigger the problem just gets really hard, rapidly getting out of reach for even the most powerful computers.

2. Meaning of P

P stands for "Polynomial time". In P the number of steps required to solve a problem which is also the amount of time it takes to solve that problem is a polynomial function of its size. So if you have a program to solve a particular problem and increase the size of the input of that program a little, the time it takes to run the program to solve that problem increases... but in a reasonable way(i.e it does not double).
"Polynomial" is a mishmash of Greek and Latin meaning "many names", which is, regrettably a pretty typical example of Maths flair for unhelpful terminology 😅.
Anyway, polynomials are functions involving n or n²(n-square) or n to other powers like these; 7n⁵-6n³+5n²
But importantly they're not exponential functions like 2ⁿ, which gets to be a ton of steps really fast as n goes up, a lot quicker than n².

So that's P, it's problems like mazes and multiplication where the number of steps required isn't that bad compared to the size of the problem.

2.5. NP

NP is all about polynomial time "checking". NP stands for "Non deterministic Polynomial time", which being math terminology is almost a mean spirited way of saying that if you had a wizard or witch inside of the computer such that it could check all possible solutions at the same time to give you an answer, then you could find a correct solution in polynomial time.

3. Current state of the art

Pretty much everybody think it's obvious that NP is harder than P and that it contains more problems than P, it's just that we haven't been able to prove it.
The bad news for fast solutions came in the early 1970's when complexity researchers realized that dozens of NP problems they were struggling with were essentially all one and the same problem(with some easy polynomial time complications thrown in here and there).
These are called NP-complete problems, and since the first batch in the 70's we've added Sudoku and protein folding, and problems underlying puzzles and games like Battleship, FreeCell, MasterMind, Tetris, Minesweeper, and making up crossword puzzles. Even classic video games like SuperMario Bros and Metroid turn out to be connected to NP-complete level traversal problems.

NP-complete is yet another maths term meaning that these problems include all the really hard parts of every NP problem. Id a fast program for solving any NP-complete comes to existence then it can be used to solve every problem in NP. The whole class would instantly collapse.
So amazingly as you can see, Sudoku is hard because it involves, literally, the same NP-complete task that makes protein folding hard.
If you come up with a profoundly faster way to play Sudoku let me know, okay? because fast protein folding would help scientists cure cancer(And we'll have our million dollars 😉).

Unfortunately the fact that a bunch of smart people have all been unsuccessful coming up with fast programs to solve what turned out to be, essentially, one and the same problem, looks like a pretty good clue that either it's impossible or the fast programs just aren't out there.

So why has it been so hard to prove P vs NP one way or the other? Well, fun fact, the exercise of proving things is an NP problem. So the P vs NP question itself is one of these problems(Do you see the paradox?). So as you can see this might be difficult... or not? We don't know.

As the field of computational complexity has developed, we've discovered a lot of complexity. The P vs NP question turns out to be the main attraction in a huge and complicated universe of complexity classes.

Beyond NP there are even harder classes of problems like EXP--the class of problems including figuring out the best move in chess that takes exponential time to even check. That whole side of problems that are at least as hard as NP-complete is called "NP-hard".

There's also Co-NP-- the class of problems where instead of being easy to check for correct answers, it's easy to instead exclude wrong answers, which may or may not be the same as NP(remember... we don't know if they're equal or not equal to each other).

There's also P-SPACE-- the class of problems that can actually be solved given unlimited time(which we don't have), but using only a polynomial amount of space for memory.

There are also problems that can be solved probabilistically in polynomial time. That class is called BPP, and it may or may not be the same as P. There's also a quantum computing analog of BPP called BQP.
All over the spectrum there are complicated little classes that would take a lot of explaining. We know there's an exponential hierarchy and there's also a polynomial hierarchy and beyond all that there are problems that are just not solvable by any computer in any amount of time or space(Example is the Halting Problem).

Conclusion

The amazing thing about this whole mess of complexity is that we're literally talking about what can be computed in a given amount of space and time. We're not just talking about the nature of computation here, we're looking at the nature of space and time themselves.
This mess of computational complexity classes, I think, ultimately has implications for physics and biology, and for our basic understanding of everything.

As an example of those implications, here's how Scott Aaronson a complexity researcher who was at MIT, explains his intuition about P vs NP:
"If P were equal to NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps", no fundamental gap between solving a problem and recognizing a solution once it's found. Everyone who could appreciate a symphony would be Mozart or Beethoven; everyone who could follow a step-by-step argument would be Gauss or Newton."

The world around us, the nature of living things and ideas, of art and genius is moulded around the deep structure of computation.
In a very real way, something connected to P vs NP shows up in the struggles of scientists and artists.

Chopin once said: "Simplicity is the final achievement. After one has played a vast quantity of notes and more notes, It is simplicity that emerges as the crowning reward of art". Computer scientists and to an extent mathematicians have been figuring out to solve all the world's problems with the help of computation but even Einstein, in his personal research for the Theory of Everything said this; "Everything should be made as simple as possible but not simpler."

Adapted from The Computational Complexity Zoo.

How easy is it to have a conversation with a chatbot and not realize it?

Bill Morrisson — Fri, 10 Jan 2020 11:59:39 +0000

Asked on Quora and answered by George Huestis here.

During a stint of internet dating I once had a conversation with a pretty girl who I assumed was a bot because she was, as near as I could tell, unable to comprehend sentences.

I tested this hypothesis by making my sentences more and more nonsensical (using imaginary words and the like) to see if she would a) say “wtf are you on?” or b) ask for my phone number (jump the shark - bot!).

She asked for my phone number.

I said: “No thanks, for [these reasons] I think you’re probably a bot trying to harvest my personal information.”

… later, for various and sundry reasons, I figured out that she was real.

An actual, honest-to-God human.

… she just failed the Turing test.

So probably it’s pretty easy, but not because the bots are so good at pretending to be human.

Is Artificial Intelligence really intelligent?

Bill Morrisson — Fri, 10 Jan 2020 10:53:23 +0000

Over the past years we've heard about the recent buzz in "Artificial Intelligence" through ideas like Machine Learning, Deep Learning or Reinforcement Learning.

Many have believed an "AI" would transcend humanity with cognitive awareness. We explore(and maybe go off topic 😉) the answer to the old age question of Alan Turing in his Imitation Game section of the paper Computing machinery and Intelligence--Can machines think?**

While we have achieved tremendous levels, have done amazing things with machine intelligence and it is seen in the news many do not know that the majority of these ideas and the algorithms implemented were actually created in the 60's. I also read about reaching the singularity where machines will gain consciousness and overtake us. I don't think that will happen. I personally don't think we will ever be able to achieve "consciousness in machines" whatever that might be. I mean we're still talking about ones and zeros -- actual metal though with extreme levels of abstraction. Generally abstraction in the domain of computer science have helped us achieve a lot doing less and less work Example: Writing Dev.to in machine language instead of Ruby 🙂. If the machines actually "overtake" us it will not be because of consciousness but because of the errors and biases we encoded in the training processes.

Don't get me wrong we will be able to achieve a lot and so much more with the advances in the field.
Machine Intelligence will assist us the same way software is assisting us in our various tasks today it's just that it will assist us in a much more powerful way than before but not necessarily replace us.

"AI" Problems

One of the issues I have with this field is the hype that's being built around it--the misconception that "AI" is about duplicating Human Intelligence entities. It is about algorithms. It is about inventing algorithms to solve problems that have previously been attributed to only human cognition. Technically, all computer programming is taking human processes, inventing algorithms and code, and then running the code on a computer. The first computer programmers were the human computers that understood the numerical methods for the numerical solution to statically processes and differential equations. It was never considered “AI” as the term had not been invented when these first programs were developed.

Another misconception is the fact that "AI" can solve all problems. The "AI" Winter of 80’s was the over selling of “Expert Systems.” The current algorithms we have are “Deep Learning” and “Machine Learning.” With these hammers, programmers are looking for the ML nails in the world. With experience and lots of failures, the boundaries of solutions for DL and ML will be marked out.

From the experience of a very old programmer;

A number of AI algorithms are now simply, algorithms. They were developed from AI research and found so useful to be members of algorithms and data structure textbooks. I expect this trend to accelerate. Examples are Depth First Search, Breadth First Search, Garbage Collection, sorting, and pattern matters matching, just to name a few. (Yes! I included sorting. Quicksort was invented to support a natural language translation program.)
Most algorithm are classified as AI because of the name of the institution it was developed in. Like the “MIT AI Lab” or “Stanford Artificial Intelligence Laboratory’s” or SAIL.

From talking with people who have been programming in the field for the last 50 years(Yes you read that right!) I have been told that most of the algorithms we use in software development today were as a result of "AI" research.

"AI" has always said it would replace everything. It has not.
The singularity invented by Vernon Vinge is cool. But does not reflect reality.
The double of computing power that he anticipated has not come to pass. Computer processor power had continued to scale with Moore’s Law and has been almost flat since 2005.

"AI" has developed wonderful and useful algorithms. Once those algorithms are put in a Algorithms / Data Structures textbook, the AI origins are forgotten! We are using "AI" algorithms on a daily basis, but we have forgot that this critical algorithms came from "AI" research. Quicksort was invented to support a program to translate Russian into English. Quicksort has a "AI" pedigree, but who remembers that? Read what Toney Hoar wrote about the invention of Quicksort.

Most of the algorithms used to do the amazing things we can now do with them were already developed(or at least started) in the 60's and 70's. Right now we see that the compute power and the amount of data needed has increased so as to use them to their seemingly full potential. An example I can think of is that of the self driving cars experiment at the Strategic Computing Initiative (1983-1993).

Navlab 1 was a Chevrolet Panel Van containing 5 racks of hardware include 3 SUN workstations, a Warp supercomputer and video hardware. With a lot of effort on the software it could do 20 mph in the late 80s.
Navlab 2 was a Huvee which could do 6 mph on rough terrain and 60 mph on the highway. It used 3 Sparc and several 68000s for its computation.

"AI" overtaking software engineers

I don't know but I find it strange when it is said "AI" will wipe out software engineers in 10 years(Yes it will but in the same way compilers did in the last 50 years).

On the thought of "AI" replacing software engineers I think that they will be able to accomplish more and more with less and less but there is no path on the horizon that would do away with programmers in the general sense.

Right now you already don't need programmers for certain tasks. You can use Microsoft Word to write a long, complex document, without needing to write custom typesetting code. You can use Excel to create quite complex spreadsheets that act as mini programs in their own right. You can use Wix or Squarespace or similar to create a web site with limited categories of interactivity.
Machine intelligence, in its current state, is not even close to being able to move the needle on any of this. It's not a matter of tweaking an algorithm a bit, or throwing more hardware at it, either.

The reason is that the core problem software engineers solve is that they translate high concepts into specific solutions. Meaning they need to understand the problem from a human perspective.

Whereas the very best AI software is currently just pattern matching and guessing at results. The absolute best you could hope for with that kind of approach is to have it create something that's already been created. Most software, on the other hand, is new. At least a little bit. So there aren't a million examples of how the result should look to train the AI on.

And even then, the exact results need to match what the users need, which again looks back to understanding what they need.

And considering the cutting edge of AI research is still mistaking the side of a truck for sky, or mangling absolutely clear speech into something laughable, the fact that “understanding” isn't anywhere near current AI is painfully evident.

Philosophy vs Science

I want to conclude with a more philosophical than scientific take. Is every thought and feeling we have simply a bunch of numbers being multiplied and added in linear algebra fashion? Are our brains, in fact, simply a neural network doing dot products all day?
That sounds almost like a Pythagorean religion that reduces our consciousness to a matrix of numbers.
I think this is why so many scientists believe general artificial intelligence is possible, as being human is no different than being a computer. (I’m just pointing this out, not commenting whether this worldview is right or wrong).
If you do not buy into this Pythagorean philosophy, then the best you can strive for is have AI “simulate” actions that give the illusion it has sentiments and thoughts. A translation program does not understand Chinese. It “simulates” the illusion of understanding Chinese by finding probabilistic patterns. When your smartphone “recognizes” a picture of a dog, does it really recognize a dog? Or does it see a grid of numbers it saw before?

I have some reservations on if we will ever be able to pass the Turing test.
As in Turing's paper I don't think we have formalized what is actually Intelligence so it will be difficult to determine if a machine can pass it.
Also if we are able to transfer "consciousness" to a computer is it really your consciousness being transferred or you are just dead then there is a computer that just imitates you perfectly?

How does a Simple Web Server Work?

Bill Morrisson — Sun, 22 Dec 2019 02:32:30 +0000

With an interest on the security of systems that are web and/or mobile based, research in that direction during my masters program is what brought me to poke into it. I have in mind to build some side projects during this program to get into the train of building web and mobile based software to be much better as a coder. Having had a stint in DevOps/Infrastructure I wish to transition back to product development as it mostly pertains to writing code and that’s where I want to continue growing my skills during this program.

I believe that to become a better developer you have to get a better understanding of the underlying software systems you use on a daily basis and that includes programming languages, compilers and interpreters, database and operating systems, web servers and web frameworks. And, to get a better and deeper understanding of those systems you have to rebuild from scratch, brick by brick, wall by wall.
As the great Confucius had put it: “I hear and I forget, I see and I remember, I do and I understand”

At this point I hope you are convinced that it’s sometimes a good idea to start rebuilding different software systems to learn how they work. In this post I will show how to build your own basic Web server.
To start, first things first, What is a Web server?

Courtesy of StackOverflow.com:

Overall it’s a networking server(which is virtual or software based) that sits on a physical server and waits for a client to send a request. When it receives a request it generates a response and sends it back to the client. The communication between a client and a server happens using the HTTP protocol. The “client” here is your browser or any other software that speaks HTTP(which is a language that helps different computers to communicate on the World Wide Web).
What would a simple implementation of a Web server look like? Here is my take on this comprehension. The example is in Python and it’s tested on Python 3.5:



import socket

HOST, PORT = '', 7777

listen_socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
listen_socket.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
listen_socket.bind((HOST, PORT))
listen_socket.listen(1)
print(“Serving HTTP on port {PORT} …”)
while True:
    client_connection, client_address = listen_socket.accept()
    request_data = client_connection.recv(1024)
    print(request_data.decode(“utf-8”))

    http_response = b"""\
HTTP/1.1 200 OK

Hello, World!
"""
    client_connection.sendall(http_response)
    client_connection.close()

Save the code above in a file called demoserver.py or download it from GitHub and run it from the command line:



$ python demoserver.py
Serving HTTP on port 7777 …

Hit Enter after typing in the following URL in your Web browser’s address bar http://localhost:7777/ and see magic in action. You should see “Hello, World!” displayed in your browser like this:

First try it and obtain the results.

Done? Great! Now let’s talk about how it actually works.

Let’s start with the web address you’ve entered which is called a URL and here is the structure;

http:// : Hyper Text Transfer Protocol
Localhost: The host name
:7777/: Port number and path(‘/’)

This is how you tell your browser the address of the webserver where it needs to connect and find the page (which is also the path and in our case the path is the root directory’/’) on the server and the server is going to fetch that for you.
Before the browser can send an HTTP request, it needs to first establish a TCP connection with the webserver. Then it sends an HTTP request over that TCP connection to the server and waits for the server to send the HTTP response back(as you can see it is a request and response cycle and all over the web that’s how connections work). And when your browser receives the response it displays it, in our case it displays “Hello World!”

Now how does the client establishes a TCP connection to the server before sending the HTTP requests and responses. To do that they both used what is called sockets. Instead of using a browser directly let’s simulate your browser manually by using telnet on the command line.

On the same computer where you’re running the webserver fireup a telnet session on the command line specifying a host to connect to localhost and the port to connect to 7777 and hit Enter:



$ telnet localhost 7777
Trying 127.0.0.1 …
Connected to localhost

At this point you have established a connection with the server running on localhost and it is ready to send and receive HTTP messages.

In the same telnet session type GET / HTTP/1.1 and hit Enter:



$ telnet localhost 7777
Trying 127.0.0.1 …
Connected to localhost.
GET / HTTP/1.1

HTTP/1.1 200 OK
Hello, World!

Fantastic! You’ve just manually simulated your browser! You sent an HTTP request and got an HTTP response back. This is the basic structure of an HTTP request;

GET: An HTTP method
/: the path(root directory in this case)
HTTP/1.1: The HTTP version

The HTTP request consists of the line indicating the HTTP method(GET, because we are asking our server to return something to us), the path / that indicates a “page” on the server we want and the protocol version.

For the sake of simplicity our webserver completely ignores the above request line as you could just type anything and you would still get back a “Hello, World!” response.

Once you’ve typed the request line and hit Enter the client sends the request to the server, the server then reads the request line, prints it and returns the proper HTTP response.

Here is the HTTP response that the server sends back to your client;

HTTP/1.1: The HTTP version
200 OK: HTTP status code
Hello, World!: HTTP response body

Let’s take it apart to understand what it actually means in detail. The response consists of a status line HTTP/1.1 200 OK, followed by an empty line and then the HTTP response body.

The response status line HTTP/1.1 200 OK consists of the HTTP version, the HTTP status code and the HTTP status code reason phrase OK. When the browser gets the response, it displays the body of the response and that’s why you see “Hello, Word!” in your browser.

And that’s how the very basic model of a webserver works.
To sum everything up; the webserver creates a listening socket and starts accepting new connections in a loop. The client initiates a TCP connection and, after successfully establishing it, the client sends an HTTP request to the server and the server responds with an HTTP response that gets displayed to the user. To establish a TCP connection both clients and servers use sockets.
Now you have a basic understanding of a working webserver that you can test with your browser or some other HTTP client. As you’ve seen and hopefully tried, you can also be a human HTTP client by using telnet and typing HTTP requests manually.

Congratulations! You have built a very simple webserver and there are things you can add like concurrency and make it adaptable to different frameworks without changing the server to suit them.