Hacker News Reader

You may want to take a look at https://cs.stackexchange.com/questions/38357/is-it-really-po...

Something along the lines of this is what you would likely need to do. Take some problem that is NP-complete. Prove it has an exponential lower bound on time complexity. You've just proved P != NP. Proof of impossibility is sufficiently common in mathematics that one of the oldest and best-known proofs of anything, Euclid's proof of the irrationality of sqrt(2), is an example of such a proof (it is impossible to express sqrt(2) as the ratio of two integers).

The philosophical issue relates more to physical non-existence. If I claim leprechauns don't exist, likely few people will argue with me, but I can't actually examine the universe outside of my own past and future light cones, so I can't really know for sure there is no part of larger existence that contains leprechauns. Even events that violate accepted physics may become possible if we live in a false vacuum that collapses to a state with a different physics at some time in the future. Proving mathematical non-existence is an entirely different animal. Trivially, any universally quantified proposition "for all X, predicate(X)" is logically equivalent to "for no X, not predicate(X)," yet proofs of such propositions abound.

> A philosophical issue of not being able to prove a negative, you really can't prove that there is not a way to solve a problem fast.

You can definitely prove negatives, and we do so all the time. There's the undecidability of the halting problem, for example: there is no algorithm that can be expressed in a Turing-complete language that can determine if a particular program will halt or not.

Another fun one is the unsolvability of the quintic. You know how there's a formula for solving a quadratic equation (https://en.wikipedia.org/wiki/Quadratic_formula)? Well, there's also one for order 3 polynomials (cubics) and order 4 polynomials (quartics). But order 5 (quntics)? There is no formula that can solve quintic equations using addition, subtraction, multiplication, division, exponents, and radicals (square roots, cube roots, etc) in the general case. The theorem actually goes even further by providing explicit examples: the equation x^5 + x^3 + 1 has a root, approximately equal to -0.83762, which cannot be expressed in terms of the operations I listed above. This is all the consequence of Galois theory.

Problems in P are about deciding whether an input passes or not, where there exists a 'turing machine/algorithm/black box' that will tell you if an input does, or does not pass in a 'fast way'. A simple example is graph coloring. The box contains a graph, you pass in a color for each node, and the box checks if there are no adjacent nodes with the same color. Note that this box has an input (the coloring) but also a sort of parameter (the graph) you can create many different instances of this box by just changing the graph.

You could also add another parameter, call it K. This will be the maximum number of colors you can use. It is still easy for the box to check if a coloring fits this criteria.

For problems in NP, there is an underlying set of boxes in P. The input to an NP problem is a set of parameters that describe a box in P. In other words, any input for an NP problem corresponds to a 'fast box'. The NP problem then asks, "is there any input this fast box will accept". Such an accepted input is called a witness, because it proves that the box created by the input to the NP problem is solvable.

In the graph coloring example, instead of having a graph, a number of colors K, and a coloring to check, you now have: a graph and a number of colors, and the question 'can we find any coloring'.

We transformed a 'check a solution' into a 'find if a solution exists'. A key element here is that someone attempting the NP problem gets to look inside the box, figure out how it works.

In your example of 'you have to guess the number I thought of', you need to hand the guesser a box that will check that number. The guesser can then look inside the box to see how it works. So a simple comparison with a fixed value allows the guesser to 'read the hardcoded value from the source code'.

Do note that the box in P has to be fully deterministic.

In an NP problem, an input describes some parameters

> That obviously P!=NP ... but your difficulty increases exponentially as n increases

> I am pretty sure there is something in this problem that makes it a not legal P/NP problem

It's not in the space of P and so isn't relevant to the problem, if I'm reading your post right, as it's exponential complexity

Wait, how is it impossible to prove a negative?

Well, I guess you can prove that there are no odd numbers in set (2,4,6), so some negatives you can prove, but in general case, I do not know how to prove that something does not exist and will not exist ever.

That's the absence of proof. It's a bit different from the proof of a negative.

Don't worry you're not the first one mentioning it so that's something that must be some kind of colloquialism somewhere but I was asking to understand what people may have meant.

To top it all, you proved a negative (by providing a counterexample) :o)

No, it's absolutely a proof.

Claim: There is no odd number in {2, 4, 6}.

Proof: 2 is not an odd number, 4 is not an odd number, 6 is not an odd number, there are no other elements in {2, 4, 6}. Therefore, there is no odd number in {2, 4, 6}.

If there was simply an absence of proof, we would be forced to conclude that we don't know whether there's an odd number in {2, 4, 6}. That's clearly not the case.

The claim "S is a set with no odd number" is equivalent to the claim "S is a set where all numbers are even", which is something I assume you agree that we can prove.

I'm not talking about the first part of the comment but the latter parts regarding the general case.

(I even wrote that he proved it himself at the end)

when proving a negativ in math, you often do a proof by contradiction

precondition: Either A is true or it is false.

question: is A false?

solution:

1. assume that A is true

2. <math stuff>

3. find a contradiction

4. ==> A can not be true

5. ==> therefor A is false

In P/NP case I would need to assume that I can solve a problem in polynomial time, and then find a contradiction. To me it is really hard to see a useful path forward from there.

> I would need to assume that I can solve a problem in polynomial time, and then find a contradiction

iirc that's actually how many of these proofs work.

> To me it is really hard to see a useful path forward from there.

yes, CS is hard.

there are resources online, that explain the general idea, e.g. [1]. But understand the specifics, you really do need a solid foundation in theoretical math and theoretical CS

[1] https://www.quora.com/What-is-a-proof-by-contradiction-in-co...

If you see a path, you'll be one million USD richer. Don't forget about us. :-)

That's what's called a "non-constructive" proof in some circles. It /doesn't/ have a useful path forward, which makes it frustrating. There are some weird sandwiches of complexity classes - like, iirc, P-SPACE, EXP, NP-SPACE - which we know to have exactly 2 subsets plus the total subset, but which constellations? Dunno.

This is different from a constructive proof. "Here we have a problem, and all algorithms so far are in O(n^3). We can demonstrate the existence of a substructure in all instances of this problem which lowers the complexity to O(n^2.978)" would be a huge constructive proof in some fields. Such a breakthrough could lead to a large number of follow-up improvements.

A non-constructive breakthrough is like "Yup, this is a barrier. No clue why though, but it's hard."

Proving a negation is not a proof by contradiction, that's just the proof of an (absurd) implication. Logic people actually write blog posts about this: https://math.andrej.com/2010/03/29/proof-of-negation-and-pro...

> I am discovering that mathematicians cannot tell the difference between “proof by contradiction” and “proof of negation”.

I am glad to learn, that I just as dumb as the average mathematician lol.

> Proving a negation is not a proof by contradiction

did I say that it is, though?