Tag Info

96

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 MTG exist and are interesting is because it has a single fixed set of (mostly) unambiguous rules, unlike law which is ever changing, horribly localized and ...

36

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 time is co-NP. Any language in co-NP is the complement of some language in NP, and vice-versa. Examples include things like non-3-colourability. The problem you ...

35

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 solve some decision problem? Because "the approximation ratio" is a term with a well-defined, standard meaning, one that means something else, and it would be ...

34

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 practice the vast majority of criminal laws are simple decision trees. Let's take, for example, section 187 (a) of the California penal code ("First Degree ...

23

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(A_2) \setminus L(A_1))$, and check whether $L(A_\Delta) = \emptyset$. Here are some more details. You can construct $A_\Delta$ using the product construction: ...

19

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 proved it). That is, for your certifier to prove that the Post correspondence problem is in NP, it needs to run in polynomial time (in terms of the size of the ...

16

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, for a total of $O(n^2)$ possible placements. Checking each one costs at most $O(m)$, where $m$ is the length of the word. In total, we obtain an algorithm whose ...

15

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 than a countable infinity, because there are only that many Turing machines (each Turing machine can be encoded as a finite string). There can be no formal ...

14

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$, then there are languages which are neither in NP nor NP-hard. For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this ...

14

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 an apple. A decision problem A is in NP if there is an integer $m$ and a decision problem B, which can be decided in polynomial time, such that: If $x \in A$ ...

14

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 problems. In an optimization setting, it makes sense because it's useful to be "close." In many environments, it doesn't make sense. It doesn't make sense to ...

13

The answer is no. Deciding whether a given context-free grammar generates a regular language is an undecidable problem. Update. I gave this negative answer to the general question Given a language specified in algebraic form, test whether the language is regular or not since context-free languages are solutions of algebraic equations in languages: ...

12

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", "certificate", "accepting path"). If $x \not\in L$, there are exactly zero "proofs". US: If $x \in L$, then there is exactly one "proof". If $x \not\in L$, there may be ...

12

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 (uniquely) encodes a program; hence, there is a bijection between $\mathbb{N}$ and the set of algorithms, so both are countable sets. Conversely, having fixed an ...

11

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.

10

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 have noted, the answer is, "yes it is", though we don't know which of the two trivial deciders is the right one. In order to frame your problem so that it's ...

10

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 rules. Legalese actually defines its terms and thus many words (but not all!) used in the law actually do have precise meanings. However, interpretation is ...

10

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 which is based on the difference between sets of cardinality $\mathfrak c$ and $\aleph_0$.) The reason lies in set theory, more specifically in the cardinality ...

9

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 length at most $3$. This can be seen by translating any grammar into an equivalent TM and then converting back. Map the resulting grammar to PCP instances; no ...

9

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 26, june 1985, pages 36-39) as an answer to a question posed by a clever student. Unfortunately, the BEATCS was at that time paper-only and the article left no ...

9

Assume you have a function like the one you described: def haltify(f): # Never fails to halt. # If 'f' halts, returns f(). # If 'f' doesn't halt, anything could be returned. ... magic ... But then someone comes along and does this: def evil(): return not haltify(evil) See the problem? If haltify(f) is guaranteed to halt for all f, ...

9

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 only if, it is provable. It can happen that there is a model in which a statement is true but not provable. What if you live in such a model? Then it could ...

9

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 proof of the undecidability of the Halting problem: we construct the decision problem "given a description of a Turing machine, does it halt in time at most $f(n)$ ...

8

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 are built up by the following rules: (a) if $x$ is a variable, then $x$ is an expression; (b) if $c$ is a constant, then $c$ is an expression; (c) if $e_1,e_2$ ...

8

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 $\Sigma$ being the underlying alphabet. Both $\Sigma^*$ and $\emptyset$ are regular languages, and in particular, are both in $P$. So yes - there are trivial ...

8

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. With these algorithms, only one of the two outcomes is determined with certainty, while the other might be incorrect. Take the Miller-Rabin test for prime ...

8

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 generalized chess is NP-complete. I reason that it's not NP-complete; not because it's easier than NP-complete problems but because it's harder. So I'll reason it's ...

8

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\}, \text{ if } y_1,y_2,y_3 \in S \text { and } (y_1 \lor y_2 \lor y_3) \text{ is a clause.}$$ $$S_x=\{x, \overline{x}\}, \text{ for all variable } x.$$ $$k=n$$...

8

NP-completeness, as with other complexity classes, has to do with problems that take an input of varying size, whose size we denote by n. In particular: A problem is NP if it's possible to determine whether any proposed solution is actually a solution with runtime polynomial in n. A problem is NP-complete if it is NP and moreover every NP problem can be ...

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