96 votes

Is legislation NP-complete?

It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt". The reason results for ...
user avatar
  • 12.3k
36 votes
Accepted

Why there are no approximation algorithms for SAT and other decision problems?

Approximation algorithms are only for optimization problems, not for decision problems. Why don't we define the approximation ratio to be the fraction of mistakes an algorithm makes, when trying to ...
user avatar
  • 141k
36 votes
Accepted

How is the traveling salesman problem verifiable in polynomial time?

NP is the class of problems where you can verify "yes" instances. No guarantee is given that you can verify "no" instances. The class of problems where you can verify "no" instances in polynomial ...
user avatar
34 votes
Accepted

Is legislation NP-complete?

Laws can include arbitrary language, and arbitrary language is able to express NP-complete logic. So in theory it would be possible to create an NP-complete or even an undecidable law. However, in ...
user avatar
  • 456
23 votes
Accepted

Is the equality of two DFAs a decidable problem?

In order to decide whether the languages generated by two DFAs $A_1,A_2$ by the same, construct a DFA $A_\Delta$ for the symmetric difference $L(A_1) \Delta L(A_2) := (L(A_1) \setminus L(A_2)) \cup (L(...
user avatar
19 votes
Accepted

Is Post Correspondence Problem in NP?

The Post correspondence problem is undecidable, and in particular it is not in NP. The reason that your idea doesn't work is that the witness is not necessarily of polynomial size (in fact, you just ...
user avatar
17 votes
Accepted

Why rectangle packing is NP-hard but maybe not in NP?

In order for a language $L$ to be in NP, there needs to be a way to certify that instance $x$ belongs to $L$. This "way" is a polynomial size witness which can be verified in polynomial time....
user avatar
16 votes
Accepted

is FIND WORDS in P?

Your language is in P. Suppose that the matrix is $n\times n$ and that the words have total length $\ell$. Each word can start at at most $n^2$ positions and be written in $O(1)$ many orientations, ...
user avatar
15 votes

How many decidable decision problems are there?

There are a countable infinity of decidable problems. There must be at least a countable infinity, because all of the languages $\{a\}$, $\{aa\}$, $\{aaa\}$, ... are decidable. There cannot be more ...
user avatar
15 votes

Why there are no approximation algorithms for SAT and other decision problems?

The reason you don't see things like approximation ratios in decision making problems is that they generally do not make sense in the context of the questions one typically asks about decision making ...
user avatar
  • 3,085
14 votes
Accepted

Do any decision problems exist outside NP and NP-Hard?

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case. If, however, $P \neq NP$, ...
user avatar
  • 1,914
14 votes
Accepted

Reconciling NP and the decision problem

By definition, all NP-complete problems are decision problems. In fact, the category of NP-completeness only applies to decision problems. Any other kind of problem cannot be NP-complete any more than ...
user avatar
12 votes

NP Problems with unique solution

Yes, the class is called UP (the U standing for "unambiguous"). David points out in the comments that another answer is US. UP: If $x \in L$, then there is exactly one "proof" ("witness", "...
user avatar
  • 4,009
12 votes

Show that there are infinitely more problems than we will ever be able to compute

Reformulating in a more mathematically precise way, what the lecturer is trying to say is this: Any algorithm can be (uniquely) encoded as a finite string of bits, and any finite string of bits (...
user avatar
  • 4,899
11 votes

Is Post Correspondence Problem in NP?

Your witness is polynomial in the size of the solution not in the size of the input. You have no way of bounding the length of potential solutions. Your proof shows that PCP is recursively enumerable.
user avatar
  • 831
10 votes
Accepted

Is Deciding Decidability Decidable?

Major edit of my original: A naive reading of your question seems to be, let $P$ be the problem $P=$ Given a language, $L$, is it decidable? Then you ask Is $P$ decidable? As D.W. and David ...
user avatar
  • 14.6k
10 votes

Is legislation NP-complete?

This is a very interesting question. Law is somewhere between everyday language with its arbitrary, constantly changing and often soft rules, and programming language with its very specific, defined ...
user avatar
  • 209
10 votes
Accepted

Show that there are infinitely more problems than we will ever be able to compute

If I understand you correctly, your question is — why a solution can be encoded by a natural number and a problem with a real number. (I assume that you understand the next phase of the proof ...
user avatar
9 votes
Accepted

Is Post's Correspondence Problem decidable with fixed word size?

For all $m \geq 3$, the problem is undecidable. Proof by reduction from the word problem of unrestricted grammars: Take an arbitrary formal grammar. W.l.o.g. all left and right sides of rules have ...
user avatar
  • 70.9k
9 votes

Is Deciding Decidability Decidable?

As we have seen in the different answers, part of the answer is in formulating the right problem. In 1985 Joost Engelfriet wrote "The non-computability of computability" (Bulletin of the EATCS number ...
user avatar
  • 27.6k
9 votes
Accepted

Undecidability of telling if a program returns true or false

Assume you have a function like the one you described: ...
user avatar
  • 5,722
9 votes
Accepted

Why we cannot prove that a computable function is total?

You misunderstand soundness and completeness of logic. You think that it says: A statement is true if, and only if, it is provable. But it really says: A statement is true in every model if, ...
user avatar
  • 28.2k
9 votes
Accepted

Prove that Hitting Set is NP-Complete

3SAT is reduced to the Hitting Set problem. Given a 3SAT $\phi$ having $m$ clauses and $n$ variables, define $$S = \{ x_1, \dots x_n, \overline{x_1}, \dots , \overline{x_n}\}$$ $$S_i=\{y_1, y_2, y_3\...
user avatar
  • 9,612
9 votes
Accepted

Are there any proofs of exponential lower bound time complexity

The Time Hierarchy Theorem states that for any (reasonable) function $f$, there exists a problem that cannot be solved in time substantially faster than $f(n)$. The proof of this is similar to the ...
user avatar
8 votes
Accepted

Is there an efficient algorithm for expression equivalence?

Your problem reduces to zero testing of multivariate polynomials, for which there are efficient randomized algorithms. Your expressions are all multivariate polynomials. Apparently, your expressions ...
user avatar
  • 141k
8 votes

What is the decision version of integer programming?

It's the same as for all NP problems; the optimisation problem is Find a valid solution $s$ that minimises¹ $f(s)$! and the corresponding decision problem is Is there a valid solution $s$ with $f(s)...
user avatar
  • 70.9k
8 votes
Accepted

The importance of the membership problem

The importance is that any computational problem where the answer is yes or no can be phrased as a membership problem in a language. The language is the set of strings for which the answer is yes.
user avatar
8 votes
Accepted

Do problems in P have a minimum number of YES and NO instances?

If a problem has only "YES" instances (resp. only "NO" instances), then the associated language, which is our formalization of a "problem" contains every word in $\Sigma^*$ (resp. no words), with $\...
user avatar
  • 16.2k
8 votes

Why there are no approximation algorithms for SAT and other decision problems?

In addition to the existing answers, let me point out that there are situations where it makes sense to have an approximate solution for a decision problem, but it works different than you might think....
user avatar
8 votes
Accepted

Why are Chess, Mario, and Go not NP-complete?

It's a common misconception that chess is NP-hard. Generalized chess may be NP-hard. Chess has an 8x8 board, generalized chess has an nxn board with many pieces. The question then becomes if ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible