Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Introduction to P vs. NP

wesammikhail.com

Post reply on HN
Print view View original

31–40 of 41 posts

Re: Introduction to P vs. NP

#31

Post by CaptainNegative »

danbruc wrote: post #22
CaptainNegative wrote: post #7

Earlier quoted context omitted.

It's kind of disappointing that GPT-4 defines NP-completeness in terms of Turing/Cook reductions while Karp reductions have been the preferred definition for the last half century or so. For example, under GPT-4's definition there is no distinction between NP-Completeness and Co-NP-Completeness. I guess that speaks to the volumes of laymen explanations out there.

What in the response indicates Turing or Cook reductions? I would say the answer does not go into nearly enough technical details to conclude anything like that, it does not even mention [polynomial time] reductions. Even among the people seeking some understanding of the P vs NP problem this is a level of technical detail essentially relevant to almost none of them. I studied computer science and if we ever discusse…

> NP-complete problems are those that, if any one of them can be solved in polynomial time, then all NP problems can be solved in polynomial time.

That is (nearly) correct under Cook reductions but not Karp reductions.

I say "nearly" because "if language L can be solved (decided) in polynomial time, then so can any problem in NP" is a vacuously true statement for any L not in P, so by this definition nearly all languages (a measure 1 fraction of them) are also NP-complete despite most of them not being in any particularly interesting complexity class.

If we escape this degeneracy by replacing the antecedent with "given access to an efficient way to decide L", then we've recreated NP hardness under Cook reductions.

Re: Introduction to P vs. NP

#32

Post by zzzeek »

bmacho wrote: post #23

For the laymans out there: pls don't just randomly use words like NP-complete or NP-hard or such, when you only know that a problem is "hard", or you don't see a trivial solution. It's exponentially annoying.

the phrase "exponentially annoying" used non ironically given the context?

Re: Introduction to P vs. NP

#33

Post by rhn_mk1 »

bmacho wrote: post #23

For the laymans out there: pls don't just randomly use words like NP-complete or NP-hard or such, when you only know that a problem is "hard", or you don't see a trivial solution. It's exponentially annoying.

> exponentially annoying.

I see what you did there.

Re: Introduction to P vs. NP

#34

Post by adgjlsfhk1 »

JohnKemeny wrote: post #13
xref wrote: post #10

> Every decade or so we come across an algorithm that takes a problem from the NP domain to the P domain Wish they’d given/linked a few examples there, anyone happen to know some off the top of their head?

PRIMES, checking whether a number is a prime number or not. It's important to note that this happens literally all the time in research. There are hundreds of problems that are easily seen to be _in NP_, that we simply don't know whether or not is in P. Many of these problems aren't that interesting, though.

Primes is a really good example because half of the proof is trivial (if I give you a factor, you can verify compositeness trivially), but verifying the other half is a pretty big number theory rabbit hole.

Re: Introduction to P vs. NP

#35

Post by thelastquestion »

nvrspyx wrote: post #25
codeflo wrote: post #24

I wonder who needs to know this who doesn’t also need to know the difference between a decision (yes/no) problem and a general problem. This is relevant because P and NP are only defined for decision problems, but all of the examples given aren’t such problems.

Can't general problems be reduced to decision problems though?

They can always be reduced, but sometimes with an unacceptably large (e.g., non-polynomial) increase in time complexity.

These are the complexity classes of Function P (FP) and Function NP (FNP), which are the function problem extensions of the decision problem classes, and require finding the value, not just answering yes or no.

A simple example of a decision problem in P but whose search problem is not known to be in FP: For a given integer x, “does there exist a non-trivial prime factor of x?” vs. “find a non-trivial prime factor of x”.

Re: Introduction to P vs. NP

#36

Post by danbruc »

CaptainNegative wrote: post #31
danbruc wrote: post #22

Earlier quoted context omitted.

What in the response indicates Turing or Cook reductions? I would say the answer does not go into nearly enough technical details to conclude anything like that, it does not even mention [polynomial time] reductions. Even among the people seeking some understanding of the P vs NP problem this is a level of technical detail essentially relevant to almost none of them. I studied computer science and if we ever discusse…

> NP-complete problems are those that, if any one of them can be solved in polynomial time, then all NP problems can be solved in polynomial time. That is (nearly) correct under Cook reductions but not Karp reductions. I say "nearly" because "if language L can be solved (decided) in polynomial time, then so can any problem in NP" is a vacuously true statement for any L not in P, so by this definition nearly all langu…

If I understand this correctly as I mostly read this just today, then Cook reductions - which is the name for polynomial Turing reductions - are the more general class whereas Karp reductions - which are polynomial many-one reductions - are a more restricted class which - to a first approximation - only allows one oracle query and must return the result unmodified.

So if I am concerned with what can be done in polynomial time, then why would I limit myself to Karp reductions? If I want to finely separate classes of problems, then Karp reductions are probably better suited as the reduction builds a much more direct link between the two problems.

That is (nearly) correct under Cook reductions but not Karp reductions.

It is however still not clear to me why this is not true under Karp reductions, because there are not necessarily Karp reductions for some problems that have Cook reductions? If so, are there two different NP-complete classes, one per reduction?

Re: Introduction to P vs. NP

#37

Post by photochemsyn »

ChancyChance wrote: post #8
chippiewill wrote: post #2

I feel like this is a pretty bad introduction to P vs NP., no? It doesn't ever actually even begin to explain what P and NP are, only what their vague properties are.

I thought it was helpful. Got a better link?

This looks good:

https://www.scottaaronson.com/papers/pnp.pdf

> "Although there’s no “purely mechanical procedure” to determine if a mathematical statement S is true or false, there is a mechanical procedure to determine if S has a proof of some bounded length n: simply enumerate over all proofs of length at most n, and check if any of them prove S. This method, however, takes exponential time. The P ? = NP problem asks whether there’s a fast algorithm to find such a proof (or to report that no proof of length at most n exists), for a suitable meaning of the word “fast.”"

"Fast" seems to mean polynomial time (which can still be a very long time, but not blowing up in the way that exponential time does). The paper gives some clear examples:

> "Think of a large jigsaw puzzle with (say) 10^1000 possible ways of arranging the pieces, or an encrypted message with a similarly huge number of possible decrypts, or an airline with astronomically many ways of scheduling its flights, or a neural network with millions of weights that can be set independently. All of these examples share two key features:

(1) a finite but exponentially-large space of possible solutions; and

(2) a fast, mechanical way to check whether any claimed solution is “valid.” (For example, do the puzzle pieces now fit together in a rectangle? Does the proposed airline schedule achieve the desired profit? Does the neural network correctly classify the images in a test suite?)

> "We’re asking whether, under the above conditions, there’s a general method to find a valid solution whenever one exists, and which is enormously faster than just trying all the possibilities one by one, from now till the end of the universe, like in Jorge Luis Borges’ Library of Babel."

The paper also discusses caveats, assumptions, limitations, etc. of the concept in an approachable manner. Then it goes off into the depths of theorem and conjecture.

Re: Introduction to P vs. NP

#38

Post by JohnKemeny »

danbruc wrote: post #36
CaptainNegative wrote: post #31

Earlier quoted context omitted.

> NP-complete problems are those that, if any one of them can be solved in polynomial time, then all NP problems can be solved in polynomial time. That is (nearly) correct under Cook reductions but not Karp reductions. I say "nearly" because "if language L can be solved (decided) in polynomial time, then so can any problem in NP" is a vacuously true statement for any L not in P, so by this definition nearly all langu…

If I understand this correctly as I mostly read this just today, then Cook reductions - which is the name for polynomial Turing reductions - are the more general class whereas Karp reductions - which are polynomial many-one reductions - are a more restricted class which - to a first approximation - only allows one oracle query and must return the result unmodified. So if I am concerned with what can be done in polyno…

> So if I am concerned with what can be done in polynomial time, then why would I limit myself to Karp reductions?

Because under Karp, SAT and UNSAT are widely different problems whereas under Cook, they're not.

You can verify SAT in polynomial time. You can not do that for UNSAT.

Re: Introduction to P vs. NP

#39

Post by karmakurtisaani »

madsbuch wrote: post #26
chx wrote: post #9

One problem here ... it needs to come with a huge caveat: this is much more a theoretical discussion than necessarily a practical one. This is to say, it's possible for a problem the best P algorithm we can find takes n^(10^82) time while the NP algorithm we can find is say (1.00000000.....(10^82 zeroes)... 1)^n. For any practical number the NP algorithm will be faster. (I used 10^82 because it's the approximate numb…

Yes, I agree. Complexity theory is probably one of the least practical fields for software _engineers_, it can even work to a detriment, because you can discouraged to find solutions to problems. On the other hand, I have had great benefit from studying PL and semantics for software engineering. It taught me to write more readable and reliable code. (From a person who studied both as a part of his master)

Quite the opposite actually! Imagine you encounter an optimization problem in your daily work and want to solve it algorithmically. You study the problem a little and find that it contains the knapsack problem as a sub case. Now you know the problem is NP-hard and don't need to waste time trying to solve it. Instead, you can think of ways to modify the problem or decide if you're fine with approximating the solution to some meaningful accuracy.

Re: Introduction to P vs. NP

#40

Post by bheadmaster »

Scea91 wrote: post #28
bheadmaster wrote: post #27

Earlier quoted context omitted.

All I've seen pretty much can. Each solution can be encoded as an integer, and as long as you can construct your query as "is solution less than N?", you can use binary search to solve the problem in log(n) repetitions of the query, which does not affect the complexity class.

I am a bit rusty on this theory but isn't the N in your case related to the output size while you would need it to be related to input size instead?

Depends on the problem, really. I've been out of school for half a decade now so I'm a little rusty too.

I remember that the Traveling Salesman can be constructed as "is the minimum path less than N" in which N represents the solution, not the size.

Post reply on HN