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

Problems harder than NP-Complete

buttondown.email

Post reply on HN
Print view View original

71–80 of 103 posts

Re: Problems harder than NP-Complete

#71

Post by yeeniee »

H8crilA wrote: post #49
g42gregory wrote: post #17

I used to be excited about complexity theory, but these days I can't help but wonder, what is the practical applications of this in real engineering problems? Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics.

If P=NP then there is no encryption and no secure digital signature algorithms whatsoever. No post-quantum variants, I mean there's nothing at all. Also, if P=NP quantum computers are probably not useful at all, perhaps they're a bit cheaper, that's all. There's a lot of NP-hard problems that you'd love to solve if you could, but you avoid them because you immediately know it's not possible. For example, you could cr…

>If P=NP then there is no encryption and no secure digital signature algorithms whatsoever.

I don't see how that follows.

A polynomial can still have factors or constants on the orders of "not in this universe's lifetime", so for all practical purposes it doesn't matter.

Re: Problems harder than NP-Complete

#72

Post by eesmith »

CJefferson wrote: post #28

One example I’ve always liked: Solving Sudoku (for general sized grids) is np-complete, but usually fairly easy. Many people write quite good sudoku solvers that can solve any 9x9 in a few milliseconds. Now, a valid sudoku is a grid which has one unique answer. What’s the smallest number of clues a valid sudoku can have? That problem is still in a 9x9 grid, and has been solved but it up at the limit of what we can do…

Neat! More at https://www.technologyreview.com/2012/01/06/188520/mathemati... from when it was solved 10 years ago:

> 7.1 million core-hours of processing time on a machine with 640 Intel Xeon hex-core processors. They started in January 2011 and finished in December.

Though the paper at https://arxiv.org/abs/1201.0749 says Sudoku solving is "only" NP-complete, so it's not really an example of "harder than NP-Complete".

Re: Problems harder than NP-Complete

#73

Post by codeflo »

thaumasiotes wrote: post #41
cvoss wrote: post #36

Earlier quoted context omitted.

That's one way to perform the computation, but that's not an NFA. The product construction involves making a single new NFA to do the job.

It is an NFA in every way except that you no longer have a single list of accepting states. "Doing two different things simultaneously" is the whole concept of nondeterminism. If you loosen the definition of "NFA" that you're working with from requiring a set of final states to requiring a function from a set of states to {0, 1}, everything will still work exactly the same way, all of your theorems will still hold, b…

> It is an NFA in every way except

So not an NFA. That's fine, you can always define "extended NFAs", and some variants are practically useful. For example, most practical "regex" implementations have features like backreferences that are very convenient, but strictly more powerful than DFAs. You just have to be aware that you lose all the well-established theory around NFAs if you do something like that.

Re: Problems harder than NP-Complete

#74

Post by chriswarbo »

g42gregory wrote: post #17

I used to be excited about complexity theory, but these days I can't help but wonder, what is the practical applications of this in real engineering problems? Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics.

> Most of the NP-Complete problems can be solved in polynomial time (but not all, of course!) with appropriate heuristics.

We need to be careful when distinguishing a "problem" (e.g. SAT) and an "instance of a problem" (e.g. "is this formula satisfiable?"). Heuristics can often help us solve real-world problem instances (e.g. seat planning for this wedding; a Hamiltonian path for this salesman; etc.), at least approximately/close-enough-to-be-useful. However, we must give resource bounds to such implementations (e.g. a timeout), since there's no way to know/check if a given instance will have worst-case behaviour until we run it.

What I find fascinating is that we can prove that some problems are just as hard to solve approximately as they are to solve optimally! https://en.wikipedia.org/wiki/Hardness_of_approximation

Re: Problems harder than NP-Complete

#75

Post by danpalmer »

bawolff wrote: post #32
cvoss wrote: post #7

> does a CS regular expression without stars have no matches? It's worth elaborating this one, because testing whether an ordinary star-free regular expression has no matches is super easy. Not sure what the author means by "CS" (maybe just "computer science"?), but the actual problem is "Does a generalized regular expression without stars have no matches?" Here, "generalized" means that we have two new operators, be…

I would assume CS regular expression means the computer sci version vs the (non-regular) regexes in popular use.

I find the need for this differentiation annoying. Referring to the class of languages is often useful, but I find most software engineers don’t have a basic understanding (and mine is only basic!) of classes of language. I always have to clarify what I mean by regular expression in these discussions. It’s disappointing that the term has been borrowed by frequently Turing complete string processing libraries.

Re: Problems harder than NP-Complete

#76

Post by chriswarbo »

Something I find interesting: if verifying a solution is cheap (sub-exponential), then we can solve that problem in exponential time by simply enumerating and checking every sequence of bytes (until we run out of RAM/disk).

That thought occurred to me when working on a system involving set permutations, where an optimal solution would have O(n!) complexity; i.e. brute-forcing the contents of RAM would be faster! (Thankfully we didn't need to be optimal; hill-climbing worked well enough!)

Re: Problems harder than NP-Complete

#77

Post by flancian »

kaba0 wrote: post #65
steeps wrote: post #15

One 2EXPTIME-complete problem that I really like is that of Linear Temporal Logic (LTL)[1] realizability. Informally, given a temporal logic formula over inputs and outputs, we can ask whether there exists some program which models the formula over all possible inputs. For instance, if we label the undesirable outputs as BAD, then we can write a formula like G!BAD (read: always not BAD), and ask if there exists a pro…

Could you perhaps recommend some book on computational complexities? My CS curriculum back then mostly included the usual Chomsky hierarchy, but was quite lean on anything other than P/NP, and most books I found were also mostly about the “basics”.

Not the parent but I really enjoyed Scott Aaronson's "Quantum Computing Since Democritus":

https://en.wikipedia.org/wiki/Quantum_Computing_Since_Democr...

Based on:

https://www.scottaaronson.com/democritus/

Re: Problems harder than NP-Complete

#78

Post by Sankozi »

Saying some problem is harder than NP Complete is like saying something is longer than "10". Without units "10" does not say anything about length. Without size function (and basic operation set) saying some problem is EXPTIME is not telling much.

Knapsack problem is common problem that has different complexity depending on how we measure it. Just googling "knapsack problem complexity" returns two answers "O(N*W)" and "NP Hard". Both are correct depending how you specify size of the problem.

Re: Problems harder than NP-Complete

#79

Post by kmill »

ithinkso wrote: post #20
cvoss wrote: post #11

Earlier quoted context omitted.

This is always fascinating to me, that there continues to be interesting structure among computational problems even after you pass the point where they aren't computable anymore. Kind of tangentially, but similar in spirit, I've often wondered about the following: You know how if you can prove False from a system of axioms, then the whole system collapses because you can prove anything from False? Well, surely not a…

I'm not sure I understand you correctly but in boolean logic it is super hard to be somewhere between truth and false. Fuzzy logic is what you're after

Here's an equivalent-ish problem:

Given a programming language, what's the smallest program that's an infinite loop?

Some languages are designed to never let you write infinite loops (every program halts in them), but maybe there's a mistake and they accidentally let some non-halting programs slip through.

Re: Problems harder than NP-Complete

#80

Post by isaacfrond »

hwayne wrote: post #19
perihelions wrote: post #12

Earlier quoted context omitted.

Pretty sure "n-node" is a typo and both vertices and edges are 2ⁿ.

No, it's a dumb mistake, I was thinking of the number of subgraphs of the N-node graph. I'll fix it.

I'm not sure the new formulation is correct either. It now states.

An n-node simple graph (...) then we can encode the graph in polynomial space!

But any n-node graph can be encoded in polynomial space. Maybe you mean to encode a 2^n node graph in polynomial space?

Post reply on HN