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

91–100 of 103 posts

Re: Problems harder than NP-Complete

#91

Post by kevinwang »

kmill wrote: post #79
ithinkso wrote: post #20

Earlier quoted context omitted.

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.

Seems like it wouldn't be Turing complete if you couldn't make an infinite loop

Re: Problems harder than NP-Complete

#92

Post by kmill »

kevinwang wrote: post #91
kmill wrote: post #79

Earlier quoted context omitted.

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.

Seems like it wouldn't be Turing complete if you couldn't make an infinite loop

Yep. Still, it turns out there's a lot you can do with non-Turing-complete languages, and it's nice knowing that a program will definitely finish.

Re: Problems harder than NP-Complete

#93

Post by kevinwang »

eterevsky wrote: post #69

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

Consider a game like go, where board size is n. This means the game tree's branching factor is O(n). Let's say the game tree's depth is O(n) too. Then what is the size of the tree?

Re: Problems harder than NP-Complete

#94

Post by luc4 »

Xcelerate wrote: post #47

For problems that are still computable, what’s the upper limit to hardness? BB(n)?

Good question. BB is certainly an upper bound.

Consider the problem P_f of getting an input x and having to compute a value >= f(x), where both the input and the output are encoded in unary. We know that BB grows faster than any computable function, so P_BB cannot be computable.

Suppose for contradiction that there was a computable problem Q with time complexity Omega(BB(x)). This means there exists a Turing Machine M that computes Q and a function T(n), such that for each n there exists an input y of length n, such that M halts after exactly T(n) steps. Moreover, T(n) = Omega(BB(x)).

Then we can construct a Turing Machine M' that computes P_BB. The idea is to run a TM for Q on a length x input and counting the number of computation steps. That number is then larger than BB(n) and thus a valid output for P_BB. Formally:

Let M be a TM that computes Q. Without loss of generality we assume that M uses a binary tape alphabet. Since T(n) = Omega(BB(x)), there exists per definition a C > 0 and an k_0 > 0 such that for all k > k_0 it holds that C*BB(k) = BB(|x|).

This implies that P_BB is computable, contradicting our initial observation. Consequently, such a Q cannot exist.

In fact, this proof works for any function that grows faster than all computable functions. This means that BB as an upper bound is not tight. For example log(BB) also satisfies this property.

Re: Problems harder than NP-Complete

#95

Post by bawolff »

danpalmer wrote: post #75
bawolff wrote: post #32

Earlier quoted context omitted.

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.

Languages change. Meanings of words drift. Regex has been used this way since the mid-70s. That is a long time now.

However, software regexes aren't turing complete. I think they are just context sensitive.

Re: Problems harder than NP-Complete

#96

Post by danpalmer »

bawolff wrote: post #95
danpalmer wrote: post #75

Earlier quoted context omitted.

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.

Languages change. Meanings of words drift. Regex has been used this way since the mid-70s. That is a long time now. However, software regexes aren't turing complete. I think they are just context sensitive.

I believe Perl regexes are Turing complete, although this is second hand info, I’ve never tried myself. Most are context sensitive though you’re right.

Re: Problems harder than NP-Complete

#97

Post by CJefferson »

eesmith wrote: post #72
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-Complet…

Thanks for the reference, and I’d misremembered the amount of CPU required.

However, I will say that while solving sudoku is np-complete, this “finding minimal” problem is harder than np-complete — it is common to have situations where solving a problem is np-complete, but then asking what is the biggest/hardest/smallest/etc problem is harder than np-complete.

Re: Problems harder than NP-Complete

#98

Post by eesmith »

CJefferson wrote: post #97
eesmith wrote: post #72

Earlier quoted context omitted.

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-Complet…

Thanks for the reference, and I’d misremembered the amount of CPU required. However, I will say that while solving sudoku is np-complete, this “finding minimal” problem is harder than np-complete — it is common to have situations where solving a problem is np-complete, but then asking what is the biggest/hardest/smallest/etc problem is harder than np-complete.

I'm not criticizing. I think less than an order of magnitude from an off-the-head memory is just fine. And after 10 years, computers have gotten more powerful. ;)

I misread the paper. I think is saying that finding the minimal size is NP-complete. Here's the abstract:

"The hitting set problem is computationally hard; it is one of Karp’s 21 classic NP-complete problems. A standard backtracking algorithm for finding hitting sets would not be fast enough to search for a 16-clue sudoku puzzle exhaustively, even at today’s supercomputer speeds."

For context, https://arxiv.org/pdf/1601.02939.pdf says:

"It has been known since Karp’s seminal 1972 paper [42] that the problem of determining whether a given set family has a hitting set of size no greater than some k is NP-complete.

Re: Problems harder than NP-Complete

#99

Post by eterevsky »

kevinwang wrote: post #93
eterevsky wrote: post #69

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

Consider a game like go, where board size is n. This means the game tree's branching factor is O(n). Let's say the game tree's depth is O(n) too. Then what is the size of the tree?

Under these conditions if you are doing a DFS over positions then you need to store O(n^2) positions in memory, considering that a position takes O(n) memory, you are using O(n^3) memory in total.

Re: Problems harder than NP-Complete

#100

Post by thaumasiotes »

codeflo wrote: post #73
thaumasiotes wrote: post #41

Earlier quoted context omitted.

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.

> You just have to be aware that you lose all the well-established theory around NFAs if you do something like that.

As I explicitly observed above:

>> everything will still work exactly the same way, all of your theorems will still hold

you don't lose any of the established theory by doing this.

Post reply on HN