### Computer Science: NP-complete Problems are Really NP-complete

First of all, let me apologize for my sloppy terminology. I've always been a better software engineer than a computer scientist.

This is how Wikipedia describes NP-complete problems:

I'd like to propose a problem that is NP-complete and show that it does not have a polynomial-time solution to it. Imagine I pick an n-tuple of random 32-bit, unsigned integers. Your job is guess what the n-tuple is. Hence, where n is 2, I might pick (376, 792), and your job is to guess that tuple. If you guess a certain tuple, I can tell you whether you're right or not. Hence, I can verify a solution in polynomial-time (it takes me O(n) number of int comparisons to verify a solution). However, to try to solve such a problem, you either have to get really lucky or you have to brute force it. If you find a method other than brute force trying every possible solution, then obviously there's something wrong with my random number generator. To use brute force to guess the solution requires O(A^n) for some constant A. Since it's "to the n", it's not polynomial-time (3nA^3 is polynomial-time since the exponent is fixed; A^n is not polynomial-time since the exponent varies with the size of n).

Now I know that some of you reading this understand the computer science a lot better than I do. Have I actually shown (at least informally) that NP-complete problems are really NP-complete? If not, can you, in lay man's terms explain what I'm misunderstanding? Thanks!

This is how Wikipedia describes NP-complete problems:

In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial-time, and also in the set of NP-hard problems so that any NP problem can be converted into L by a transformation of the inputs in polynomial-time.Note that it says, "As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today." I haven't seen the proof for it, but I've also heard that if you could prove that one NP-complete problem does not have a polynomial-time solution to it, then that would prove that none of them have a polynomial-time solution to them. The theory is a little over my head, but I'm going to take a shot.

Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.

While a method for computing the solutions to NP-complete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. NP-complete problems are often addressed by using approximation algorithms.

I'd like to propose a problem that is NP-complete and show that it does not have a polynomial-time solution to it. Imagine I pick an n-tuple of random 32-bit, unsigned integers. Your job is guess what the n-tuple is. Hence, where n is 2, I might pick (376, 792), and your job is to guess that tuple. If you guess a certain tuple, I can tell you whether you're right or not. Hence, I can verify a solution in polynomial-time (it takes me O(n) number of int comparisons to verify a solution). However, to try to solve such a problem, you either have to get really lucky or you have to brute force it. If you find a method other than brute force trying every possible solution, then obviously there's something wrong with my random number generator. To use brute force to guess the solution requires O(A^n) for some constant A. Since it's "to the n", it's not polynomial-time (3nA^3 is polynomial-time since the exponent is fixed; A^n is not polynomial-time since the exponent varies with the size of n).

Now I know that some of you reading this understand the computer science a lot better than I do. Have I actually shown (at least informally) that NP-complete problems are really NP-complete? If not, can you, in lay man's terms explain what I'm misunderstanding? Thanks!

## Comments

Everyone studying these problems has full access to every other lemma and theorem out there. Getting "lucky" is often a simple matter of combining several of these lemmas and theorems together in interesting new ways.

It's important to note that "lucky" is not the same as "trial and error" or "random."

I think you also have to prove that your proposed problem can be transformed into a known NP-Complete problem in polynomial time. Use the traveling salesman as a target.

To which I responded:

Hmm, here is a way to convert the problem into the traveling salesman problem. Number each of the cities. Your trip among the cities is a tuple of numbers. If the cost of each trip between cities is completely random (i.e. if you don't assume that close cities are cheaper to travel between than distant cities), then the optimal solution is an N-tuple of city numbers. Either way, you have to at least partially examine every possible solution.

A decision problem for tuples of integers is basically just a set of such tuples. And given a tuple, you must determine whether it's in the set. Note that there is nothing adversarial here: you can't keep the set "secret".

So, if the set only contains one tuple, the algorithm is simple: compare argument tuple with this tuple; if they are the same, return "yes", otherwise return "no". This problem is in P (and even in L).

Let's say I have an encrypted message. I already know what it's supposed to say, and I already know the algorithm that was used to encrypt it. What I don't know is the key used to encrypt it. My goal is to find the key so that I can decrypt other messages.

The key happens to be an n-tuple of integers. The algorithm is such that there is exactly one n-tuple that can be used to decrypt the message in such a matter that I end up with the original message. Furthermore, the algorithm is such that the person who picked the key had the freedom to choose any n-tuple of 32-bit, unsigned integers.

Given all that I know, I must decide what the key is.

Is N know to the guesser?

Not sure if this is a "decision" problem but once you guess a no more that is bigger that the solution , chose the largest 32bit integer, then the problem is polynomial. Just count 1,2,3,4,5 ( keeping in mind that the tuples a the same size as the integers and therefor can be ordered/sorted/counted.

http://en.wikipedia.org/wiki/Countable_set

I think you've only given a single direction.

2. For example, say your algorithm just XORs plain text with repeated copies of the key. It does satisfy your conditions (you can use any n-tuple as the key and there is no more than 1 key which converts the given plain text to the given encrypted text), but it's trivial to find the key: just XOR plain and encrypted messages.

3. So you need to pick some algorithm and prove that there is basically no other way to find the key except by guessing. And well, so far nobody has been able to do that!

betterapproach than trying to defend it against other people breaking it (though that's not unreasonable). Confirmation bias alone is a big danger and you learn more about what makes the problemand your proposed solutiontick by finding flaws.There are a lot of problems with the proof (many have been pointed out), but I'd start with:

"Hence, I can verify a solution in polynomial-time (it takes me O(n) number of int comparisons to verify a solution)."

There are a number of issues other commenters have raise, but, here's the one I think is key:

Who is doing the verifying? If it's the person (really *process*) with antecedent knowledge of the answer, then they aren't really verifying the the answer, they are doing a look up. Let P be the proposed solver of this problem, V be an

independentverifier and Y be you, the person who made up the number. V is independent in the sense that there is no communication between V and Y other than the knowledge of what the problem is (i.e., guess a randomly generated number).P provides a possible answer...how does V verify it? It can't! There's no verifying that the answer is right because there's no way to tell what the right answer is except by asking Y. Once we get an answer from Y we can

compareanswers in linear time. But V doesn't have any way of knowing that Y didn't lie! Thus it cannot verify the answer.Imagine there were Y1 and Y2, and let N=2. It's highly likely that Y1 and Y2 will generate different tuples and suppose that is the case. Now P is told, "Solve this problem for N=2". Which answer is the right answer such that V should confirm it? Y1's or Y2's? There's no being right here. Thus this isn't the right kind of problem. (Note, we know of problems that are

strictly harderthan NP-COMPLETE problems. So you have to be careful that you haven't shown that one ofthemdoesn't have a polynomial solution...that would just tell us what we already know.)Bijan, "stupidly clever" is what I was aiming for. The proof for the halting problem was "stupidly clever."

I don't know how else to put that I think your approach, esp. in the way you double down in this last comment, is not likely to lead you to a good understanding of the issues (or of complexity theory). You also are running the risk of kooking out. ("Trying to be stupidly clever...like the halting problem" is pretty close to "I have a proof that special relativity is false" or taking your hot cousin to the prom or "I'm like Galileo and you are like the pope, oppressing my scientific geniusness!!!" I don't think you are *there*, just uncomfortably close by.)

I think the P = NP question is one of the most amazing and fun things to explore, so I strongly encourage you to do so. I just rather suspect that the current approach is particularly efficient (e.g., afaict, you aren't even in the ballpark; cf my other comment).

I find the Gary and Johnson complexity book to be really nice for getting into the groove.

* I don't think you can do a binary search since the response is "yes" or "no", not "you're too high" or "you're too low".

* It was a mistake to use 32 bit unsigned ints. Vincent pointed out the flaw in that. I'd suggest using an N-tuple of arbitrarily large whole numbers.