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

31–40 of 103 posts

Re: Problems harder than NP-Complete

#31

Post by JoeDaDude »

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

I remember my head exploding upon seeing a presentation on the work of Larry Stockmeyer. Though he was an academic working in the obscure discipline of theoretical computer science, he ended up being named in a science fiction novel.

Summary paper: https://lance.fortnow.com/papers/files/beyondnp.pdf

Slide show: https://www.slideserve.com/leda/beyond-np-the-work-and-legac...

Re: Problems harder than NP-Complete

#32

Post by bawolff »

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.

Re: Problems harder than NP-Complete

#33

Post by bawolff »

CJefferson wrote: post #27
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.

In my experience of NP-complete research, there tends to be “real world bias”. There are problems we can mostly solve in polynomial time, and those gets lots of study and people talk about them a lot. There are other problems which are equally valid np-complete problems, for example reversing most encryption and hashing algorithms (with hashes you obviously don’t get a unique reversal, but you can get something), whi…

Finding a hash pre-image is kind of an artificial problem, because hash algorithms are specificly chosen to make that hard.

I would assume those things are not np-complete and just np.

Re: Problems harder than NP-Complete

#34

Post by thaumasiotes »

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.

Re: Problems harder than NP-Complete

#35

Post by semihsalihoglu »

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

I hadn't heard for this but this sounds very similar to the definition of polynomial hierarchy: https://en.wikipedia.org/wiki/Polynomial_hierarchy

What has fascinated me (if I'm not mistaken) when I was learning about computational complexity was that P=NP implies that the polynomial hierarchy (so this infinite classes of problem) collapses to P, so all problems in the polynomial hierarchy are solvable in polynomial time.

Re: Problems harder than NP-Complete

#36

Post by cvoss »

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.

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.

Re: Problems harder than NP-Complete

#37

Post by [deleted] »

zeroonetwothree wrote: post #18
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.

Much of theoretical CS is just math and has no real practical consequences. Once in a while you do encounter something useful but it’s rare.

[deleted]

Re: Problems harder than NP-Complete

#38

Post by cvoss »

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

No, fuzzy logic is not what I'm after. Nor even the truth or falsity of single statements. I'm interested in the degree to which an entire inconsistent system of logic is inconsistent.

Re: Problems harder than NP-Complete

#39

Post by legobmw99 »

semihsalihoglu wrote: post #35
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...

I hadn't heard for this but this sounds very similar to the definition of polynomial hierarchy: https://en.wikipedia.org/wiki/Polynomial_hierarchy What has fascinated me (if I'm not mistaken) when I was learning about computational complexity was that P=NP implies that the polynomial hierarchy (so this infinite classes of problem) collapses to P, so all problems in the polynomial hierarchy are solvable in polynomial…

Your understanding is correct: https://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem

Re: Problems harder than NP-Complete

#40

Post by zbobet2012 »

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

Post reply on HN