Hacker News Reader

Comment by wddkcs | Hacker News Reader

Can you really separate the two? For something like NP-completeness, I'm having trouble conceptualizing how a proof for existence would not require demonstration.

View on HN

Yes, there are non-constructive proofs for the existence of polynomial time algorithms [1]. The Robertson–Seymour theorem [2] is a common example, it shows that certain classes of graphs can be characterized by finite sets of forbidden subgraphs [3] which can be checked for in polynomial time but it does say what those sets of forbidden subgraphs are or how they can be found.

[1] https://en.wikipedia.org/wiki/Non-constructive_algorithm_exi...

[2] https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theo...

[3] More precisely forbidden minors.

An example for such a proof would be using the probabilistic method. However, even if we are ignoring some artificial problems, there are some "natural" problems that are known to be in P that we do not have algorithms for.

https://en.wikipedia.org/wiki/Non-constructive_algorithm_exi...

Also see:

https://cs.stackexchange.com/questions/92087/are-there-any-p...

Thank you- your link to non-constructive proofs led me to this HN comment, which seems to flesh out why such proofs are not applicable to P = NP

https://news.ycombinator.com/item?id=29022963

Im just reading about constructive vs. Non-constructive proofs, but my intuition seems to be that a proof would P = NP would have to be constructive.

https://news.ycombinator.com/item?id=19720511

That "proof" is applicable to any algorithm that "exists". As "an algorithm exists, so we can enumerate all of the Turing machines "in parallel" and find it" would work for anything in P, other algorithms as well. However, good luck actually running that algorithm... Enumerating Turing machines in parallel, executing them, and n could be many times larger than the age of the universe. You want something that you can execute, not something that in theory exists.

The kind of ultra-shoddy "construction" you get from "Here is an impossible to build machine that would give us the proof" would still not get you a demonstration. It would still be something we don't have the algorithm for.

Probably very silly, but for a long time, when I've seen "p=np" thrown around, I've always considered it some kind of matrix math problem where n could be substituted by an identity matrix which itself could be substituted by some kind of sampling (which would represent observations of events bounded by np-space) unitary matrix multiplied by its conjugate transpose[0](thus, p = np -> p = ip -> p = uu*p, or p= u*up), which seems like that would be in line with a probabilistic method, is that the case? Or is this a wrong way to think about this?

[0] https://en.wikipedia.org/wiki/Unitary_matrix

Substitute the N? No, you can't substitute "try every solution simultaneously" by "some kind of sampling".

Let's use a very simple example. How could sampling help you find the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4?

You couldn't sample from anything if the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4 is never used to encrypt any text. Though if the password that hashes to 21e400789a8ad12adb89d72ca8d92cc72400fea4 goes on to be used to encrypt any text, and one has access to the cipher text, then you can sample from the cipher text.

Okay, so you can't design anything for my example problem? It's not being used to encrypt anything, all you get is the hash. Which is solvable very very fast with an NP machine. If you can't apply your idea to that, you haven't found a general solution.

Yeah, a general solution wouldn't be useful in the wild against keys that are never used in the probabilistic approach i am thinking of, observations of cipher text are needed (which isn't unbounded).

The point is this. Here is a nondeterministic algorithm that proves the problem the poster above was formulating is in NP:

  matching Passwords = choice(AllStrings, str -> hash(str) == desiredHash)

Assuming hash(str) has polynomial time, the nondeterministic algorithm above is clearly polynomial as well. Here `choice` is not a function, it is an elementary nondeterministic operation, one which evaluates the given function on each value in the input variable in O(1). AllStrings is the set of all strings, maybe limited to some max length if desired (otherwise, matchingPasswords will be an infinite set itself).

As far as it is known, there is no way to replace this with any sampling method that would take polynomial time. Of course, this is not proven, it is a related problem known as BPP=NP. BPP is the class of problems for which Bounded-error Probabilistic algorithms with Polynomial time complexity exist.

I don't understand what you mean. NP is not N multiplied by P, it is the name of a set, the set of all problems which can be solved by a Nondeterministic algorithm with Polynomial time complexity. P is the name of the set of all problems which can be solved by a deterministic algorithm with Polynomial time complexity. The P=NP problem is a set identity problem, it's not an algebraic equation.

Note that here nondeterministic algorithm can be thought of as an algorithm which can try every value in parallel when faced with any choice, even an infinite amount of values. For example, a nondeterministic algorithm can try every number in R in parallel. There is no known way to replace this nondeterminism with probabilistic methods.

Yes, proofs don't have to be constructive.

Consider proofs by contradiction, you could potentially show that if such an algorithm does not exist some important true statement would be rendered false.

Sure. There is definitely a googolth digit of pi. Computing what the digit is, however, is not necessary to prove that such a digit exists.

My intuition was that if a proof for P = NP exists, it would be incomparable to the kind of Pi example you provide- Pi is defined as an irrational ratio, so the existence of whether x digit of Pi exists. It would instead be like saying, 'the x digit of P is 7, and here is a proof that is not a straight calculation'. The idea of a proof which can demonstrate knowledge of X digit of Pi, without verification, doesn't click for me.

It's a quite bad analogy because the googolth digit of pi is completely constructive. (You don't need to calculate it, but it is constructive)

P = NP proof could be not constructive.

Proving the Nth digit of pi exists is not (necessarily) constructive.

Though to make it an actual proof and not a truism you might say "when writing pi in the shortest decimal representation, there is a millionth digit".

Proving pi is irrational would suffice, without actually calculating the first million digits.

Note: finding arbitrary digits of pi doesn't require finding the preceding digits. It's kind of freaky.

https://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%9...

suppose NP-complete problem X is in NP but not P. From this premise I arrive at a contradiction and conclude X is in P. Thus P=NP with no polynomial algorithm for solving any NP-complete problem provided

Reply on news.ycombinator.com