Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
95

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


35

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


33

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


32

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


28

As already stated in the comments, it depends on the definitions, as usual. My attempt to answer this needs quite a few definitions, so this will be another example of my inability to give concise answers. Definition: An optimization problem is a tuple $(X,F,Z,\odot)$ with $X$ the set of suitably encoded (strings) instances or inputs. $F$ is a function ...


26

I think you misunderstood what it means to solve a diophantine equation, and Matiyasevich's indecidability theorem. Matiyasevich proved that for every RE set $S$ there is a diophentine equation $f(n;x_1,...,x_k)$ such that $n \in S$ only if there exists integer coefficients $x_1$,..,$x_k$ such that $f(n;x_1,...,x_k) = 0$. In particular, the halting problem ...


22

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


18

SMT solver is a SAT solver + decision procedure A SAT solver is a solver for a decision problem: the SAT problem is a decision problem. Additionally, this decision problem is "self-reducible": The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment ...


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

The problem of deciding language containment in NFAs is $PSPACE$-complete. To prove this, it is easy to reduce from the universaility problem for NFAs (testing whether $L(A)=\Sigma^*$) So, in a way, you have to determinize, but you may do so on-the-fly. Your observation about co-NP is wrong (but nice). Such a witness can indeed be checked in polynomial ...


14

The definition of the decision version of independent set is the following: Given as input a graph $G = (V,E)$ and an integer $k \in \mathbb{N}$, does there exist a set of pairwise non-adjacent vertices $I \subseteq V$ of size $|I| \geq k$? The problem is polynomial time solvable if you consider $k$ to be constant, i.e., you can solve the problem in time $\...


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


13

If A reduces to B, does B reduce to A? No. For a really contrived example, any possible computable problem A is reducible to the Halting Problem: just pass as input the algorithm that solves the problem A but with a while(true) tacked at the end after either the true or false case. However, we know that the Halting problem isn't computable so it can't be ...


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


13

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


12

The task of deciding membership is: given any input $x$, decide wether $x \in L$, i.e. compute the following function: $\qquad \displaystyle \chi_L(x) = \begin{cases}1 &x \in L \\ 0 & x\notin L\end{cases}$ On the other hand, the task of verifying membership is: given any input $x$ and a (proposed) proof (or witness) of membership, check quickly ...


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


11

Traditionally, in computability theory all problems are encoded in terms of numbers, or sometimes strings of bits $0$ and $1$. This is a very "low level" kind of thing, it is like programming directly in machine code. The reason for doing this is mostly historic. Gödel originally encode first-order logic in terms of numbers to prove his incompleteness ...


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.


11

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


11

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


10

I'm assuming that you're thinking of the Euclidean traveling salesman problem, where $c$ and $v$ are vectors in $\mathbb{Z}^{2n}$, with two coordinates for each city. Let $minTSP(c)$ denote the length of the minimum traveling salesman tour for the cities with coordinates $c$. Then your problem asks whether $$ minTSP(c + v) \ge min TSP(c) + x. $$ But then ...


10

An equivalent definition of NP is that it consists of all problems that are decidable (not just verifiable) in polynomial time by a non-deterministic Turing machine. NTMs are known to be no more powerful than TMs in the sense that the set of problems decidable by NTMs is identical to the set of problems decidable by TMs, so clearly by this definition there ...


10

No. E.g. the Halting problem is a decision problem which is NP-hard but not in NP and therefore not NP-complete. In normal usage yes, because an NP-complete problem must be in NP and NP is a class of decision problems. But see Decision problems vs “real” problems that aren't yes-or-no.


10

Obviously this can be solved with the same complexity as boolean SAT. The question is, can we do better. The answer is no: this problem is NP-complete. You can show it is NP-complete by reducing a regular CNF formula to "quasi-monotone" CNF, as follows: Since you cannot use positive terms in general, what you want is a new, equivalent, variable in-place of ...


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


9

Here is a simple argument to show that they are undecidable, i.e. there are no algorithms to check if a given algorithm is optimal regarding its running-time or memory usage. We reduce the halting problem on blank tape to your problem about running-time optimality. Let $M$ be a given Turing machine. Let N be the following Turing machine: $N$: on input $n$...


9

The HAMPATH complement ("G does not contain an Hamiltonian path from s to t") is in co-NP; to be more precise it is co-NP complete (it is easy to prove that $L$ is NP-complete if and only if its complement $\bar{L}$ is co-NP-complete). The question if it is in NP is open. But since HAMPATH is NP-complete, if its complement is in $\mathsf{NP}$ then $\...


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