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

41–50 of 103 posts

Re: Problems harder than NP-Complete

#41

Post by thaumasiotes »

cvoss wrote: post #36
thaumasiotes wrote: post #34

Earlier quoted context omitted.

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

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, but intersecting two NFAs will consist of adding one state and adjusting the accept function.

Re: Problems harder than NP-Complete

#42

Post by opportune »

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.

Most likely they mean Cartesian product instead of cross product.

Also whatever you are describing is not an intersection per se as it’s not a permutation of the two possible combined states, it’s a construction for doing certain computations on intersected NFAs given its constituents. If each of two intersected NFA has three states the intersection can be up to 9 (the cardinality of the Cartesian product) states

Re: Problems harder than NP-Complete

#43

Post by ouid »

Laakeri wrote: post #21
krick wrote: post #10

How hard is computing Ramsey numbers, BTW? Is there a word for that?

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.

Re: Problems harder than NP-Complete

#45

Post by blt »

elteto wrote: post #44

Coming to a software interview near you: “Define a Vector Addition System as follows: you have a starting vector S, like [...] You have 45 minutes, I expect working code.”

Just because the complexity is high, doesn't mean the algorithm is complicated.

Re: Problems harder than NP-Complete

#46

Post by cwmoore »

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…

That is an interesting contrast. I don't know the smallest number of clues a kakuro puzzle can have, but I made easier ones with many clues, and harder ones, that also have many clues, generously fitting the heart shape, but I'd only be willing to spend tens of CPU hours on optimizing it.

https://www.curtiswmoore.com/kakuro/v0.2/kakuro_with_solver....

Re: Problems harder than NP-Complete

#48

Post by nl »

cvoss wrote: post #11
raatmarien wrote: post #2

And then beyond these decidable problems, there is a whole hierarchy of harder and harder undecidable problems, which I think is really cool as well. https://marienraat.nl/blog/posts/hardest-computational-probl...

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…

Steven Wolfram talks about related concepts a lot in the frame of his "computational irreducibility" concept. It's interesting to think that there could be systems composed of comparatively simple rules but computing that first proof of False could take longer than the universe.

It's interesting, and Wolfram explains it well. You do need to ignore the ego though.

Re: Problems harder than NP-Complete

#49

Post by H8crilA »

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 create optimal neural networks that might be 10x? 100x? more powerful for the same size/cost as GPT-4 is.

This stuff is likely so beyond the reach of today's knowledge that it would be like talking about quantum mechanics and integrated circuits running at GHz speed to Euclides. It's like when Paul Erdős talked about the Collatz conjecture: "Mathematics may not be ready for such problems."

Re: Problems harder than NP-Complete

#50

Post by nl »

zbobet2012 wrote: post #40
raatmarien wrote: post #2

And then beyond these decidable problems, there is a whole hierarchy of harder and harder undecidable problems, which I think is really cool as well. https://marienraat.nl/blog/posts/hardest-computational-probl...

One of the more interesting undecidable problems out there is kolmogorov complexity. It basically asks the question: given a string what is the smallest program that generates that string. Which fundamentally is the question of compression. So these undecidable problems actually have a lot of practical value. https://en.m.wikipedia.org/wiki/Kolmogorov_complexity

And Kolmogorov complexity is used by Shane Legg (DeepMind founder) and Marcus Hutter (Hutter prize etc) in their paper "A Formal Measure of Machine Intelligence"

http://www.vetta.org/documents/legg-hutter-2006-formal-measu...

Post reply on HN