# Tag Info

### 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 ...
• 13.4k
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 ...
• 160k
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 ...
• 81.7k
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 ...
• 466

### Why are computability problems always written in full caps?

After the Cook-Levin Theorem Richard Karp realized that the complexity of computational problems could be compared. His paper was prepared in a type-writer font, and used underlining and all-caps for ...
• 30.7k
Accepted

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(... • 277k 22 votes Accepted ### Is SAT an existential question? The SAT problem is a decision problem. It means that an algorithm that solves SAT must answer true or false, and not necessarily ... • 15.7k 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.... • 277k 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, ... • 277k 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 ... • 81.7k 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 ... • 3,351 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$, ... • 3,094 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 ... • 277k 14 votes ### Why are computability problems always written in full caps? In the area of discrete mathematics, sets are usually typeset in capital letters. The above problem classes are sets of problems, e.g. SAT is the set of all boolean satisfiability problems. Thus, the ... • 1,274 13 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 (... • 5,027 12 votes ### Is SAT an existential question? If you have variables x1 to xn, and you decide in polynomial time whether the problem can be satisfied or not, then if it can be satisfied, you set x1 = true and check if it can still be satisfied. If ... • 30.1k 11 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, and ... • 30.4k 11 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 ... • 2,521 11 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 ... • 576 10 votes ### Why are Chess, Mario, and Go not NP-complete? Your understanding of what makes chess NP-Hard is slightly flawed. Yes, a nondeterministic machine is able to "play perfectly". But the language of chess is, $$Chess = \{Pos \quad | \quad \text{White ... • 4,292 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 ... • 209 9 votes Accepted ### Undecidability of telling if a program returns true or false Assume you have a function like the one you described: ... • 5,852 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\... • 9,837 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 ... • 13.2k 9 votes Accepted ### What is a witness string? I unable to understand the concept To give a concrete example, imagine you have a box of 4-digit combination padlocks. All those padlocks are closed, but some of them have a defect and no code can open them. Given a padlock, you want ... • 15.7k 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. • 81.7k 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$\...
• 17.2k
No. The optimization problem is "How big is the biggest $X$?" and the decision problem is "Is there an $X$ that is bigger than $y$?" Solving the decision problem simply involves ...