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

61–70 of 103 posts

Re: Problems harder than NP-Complete

#61

Post by CaptainNegative »

ouid wrote: post #43
Laakeri wrote: post #21

Earlier quoted context omitted.

For binary-encoded input it is in 2-EXPTIME by trying all graphs of size exponential in the input number and testing all subsets of the given size. Would be surprising if any hardness result for complexity classes would be known.

Wait, that doesn't make sense, does it? The Ramsey function grows so fast that Peano arithmetic cannot prove that it is total.

I'm not sure what you're referring to here. Ramsey's theorem is constructive enough that you can extract an upper bound of 4^k on the kth diagonal Ramsey number, and the (j,k)th Ramsey number is bounded from above by the max(j,k)th diagonal number.

Re: Problems harder than NP-Complete

#62

Post by dragontamer »

#P Complete is my favorite 'harder than NP Complete' class.

Discovering if a 3-SAT problem has Zero solutions is a famous NP complete problem.

#P is very easy to understand as an extension. Instead of asking for 'Is there more than zero solutions?', you ask 'How many solutions are there?'

And bam, you've gone from NP complete to #P complete. One of the easiest ways to make NP complete problems even harder.

--------

All NP Complete algorithms can be solved by a #P complete algorithm. Just ask for the count, return true if count > 0. Return false if count == 0.

Therefore, NP Complete is proven to be easier (or worst case, tied with) #P Complete space.

Re: Problems harder than NP-Complete

#63

Post by suyjuris »

thaumasiotes wrote: post #34
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…

> You may recall that constructing an intersection automaton involves a cross product of NFAs I'm not sure what you mean by "cross product" here, but there's nothing multiplicative involved. You just run both NFAs simultaneously. This gives you a number of states to track equal to the sum, not the product, of the two NFAs being intersected.

You are thinking of the union, where you can indeed just put the two NFAs “side-by-side”. This does not work for the intersection though, there you need the product construction.

Re: Problems harder than NP-Complete

#64

Post by [deleted] »

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…

[deleted]

Re: Problems harder than NP-Complete

#65

Post by kaba0 »

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”.

Re: Problems harder than NP-Complete

#66

Post by ouid »

CaptainNegative wrote: post #61
ouid wrote: post #43

Earlier quoted context omitted.

Wait, that doesn't make sense, does it? The Ramsey function grows so fast that Peano arithmetic cannot prove that it is total.

I'm not sure what you're referring to here. Ramsey's theorem is constructive enough that you can extract an upper bound of 4^k on the kth diagonal Ramsey number, and the (j,k)th Ramsey number is bounded from above by the max(j,k)th diagonal number.

My mistake. I, and I suspect the original commenter, was thinking about the strengthened finite Ramsey theorem. From wikipedia: https://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theor...

For any positive integers n, k, m, such that m ≥ n, one can find N with the following property: if we color each of the n-element subsets of S = {1, 2, 3,..., N} with one of k colors, then we can find a subset Y of S with at least m elements, such that all n-element subsets of Y have the same color, and the number of elements of Y is at least the smallest element of Y.

This function is outside the reach of Peano arithmetic.

Re: Problems harder than NP-Complete

#68

Post by enriquto »

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.

Why do you say that? A problem being in P does not necessarily mean that it's easy, or that it is solvable at all in practice. Recall that the class P contains problems that require a running time of O(n^A(6,6)), where A is the Ackerman function. This is an inconceivably large number, and there's no realistic expectation to solve such a problem for even minuscule values of n, like n=2 or 3.

The class P is huge, and our puny linear and quadratic algorithms can only solve its lower, trivial levels. We have not yet started scratching the surface of the enormous set P, yet some of us are arrogant enough to call all of it "easy".

For all we know, it may well be that P=NP but have no practical consequences whatsoever.

Re: Problems harder than NP-Complete

#69

Post by eterevsky »

> most EXPTIME-complete examples fall in one of two categories. First, game problems. Given a configuration of an NxN Go/Chess/Checkers/Shogi board, does player 1 have a winning strategy?

It seems like these should be solvable in PSPACE, provided there's a polynomial limit on the number of moves in the game, since you can just do a recursive minimax search.

Re: Problems harder than NP-Complete

#70

Post by henrik_w »

User23 wrote: post #22

For anyone with an interest in going a little deeper, in my opinion the best textbook on the subject is Sipser's Introduction to the Theory of Computation . It's truly introductory, so anyone who is smart enough to program will be able to follow, if they do the work. [1] https://www.goodreads.com/en/book/show/400716

Thanks, looks fantastic. Just ordered it.
Post reply on HN