# Tag Info

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

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

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

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

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

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

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

7

$L_1$ and $L_2$ are always countably infinite, and thus "equally big". If any language is finite, then it is "constant time" recognizable.

6

EXPSPACE is not the most inclusive computational complexity class. There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there are an unlimited number one could define). The space hierarchy theorem shows that for each $f(n)$, there are languages that can be decided in space $f(n)$ but ...

6

Every algorithm can be described by a finite string, and so there are only countably many algorithms. In contrast, we can describe every decision problem as an infinite decimal in base 2, and moreover this is a surjective mapping: every number in $[0,1]$ can be "decoded" into a decision problem. Therefore there are uncountably many decision problems. The ...

5

I think what's missing in the excellent answers so far is that computation theory assumes known, certain, input data, whereas legislation is operating in a field where the facts are usually uncertain and fuzzy. Criminal law, for example, concerns itself with the "intent" or "state of mind" of a defendant, which can never be known with certainty. The divorce ...

5

Note that there's always a prime between $p$ and $2p$ for any $p$ thus we can eliminate $n$ as a complexity parameter, as for any non-trivial instance we have $n < p$. The complement (there exists a prime in range $[p, p+n]$) is quite easy (due to the shoulders of giants). There are various well-known polynomial size certificates of primality of $q$ ...

5

Let $M$ be a $n \times n$ matrix. And I am searching a word $l_ll_2 \dots l_k$ of length $k$. Now first we search $l_1$ in $M$. It takes $O(n^2)$ time. For each successful search, we look at all eight direction (up to down, down to up, left to right, right to left, diagonal-left-up, diagonal-left-down, diagonal-right-up and diagonal-right-down) and check ...

4

The language $\{a^n : \text{ the$n$th Turing machine halts on the empty string} \}$ is undecidable. In fact, a random unary language is undecidable almost surely, for the simple reason that there are only countably many computable languages.

4

Rather than going to talk about algorithms and more about SAT, this answer tries to show that there is more than just one kind of logic and that there are also different kinds of approaches. I won't go into detail much but rather provide a list with some topics and keywords that should form a good basis to do some research: Higher order logic There are ...

3

No. As an example of a language that is decidable but does not have a context-free grammar is the language over the decimal digits that only contains the prime numbers.

3

You are correct. The problem of deciding "$L$ is a recursively enumerable language" is undecidable. However, that does not make $L$ itself undecidable. Do not mistake a language for its class! Telling whether $L$ is in a class is definitely not the same as deciding membership in $L$.

3

It is unknown whether context-free languages can be decided in logarithmic space. The best known result shows that they can be decided in nondeterministic space $O(\log^2 n)$. It is also known that if all context-free languages can be decided in deterministic logarithmic space then $\mathsf{L} = \mathsf{NL}$, which is considered unlikely. For references, ...

3

For regular languages, we have $$\text{REG = DSPACE}(O(1)) = \text{NSPACE}(O(1))$$ where REG is the class of regular languages. This can be easily seen from the equivalent formalisms of regular languages. A language is a regular language iff it is the language accepted by a deterministic finite automaton. A language is a regular language iff it is the ...

3

Problems of the type "Count the number of [object]", where "[object]" is something that can be verified in polynomial time, are essentially what defines the class $\#P$ ($\textrm{Sharp-}P$). $\#P$ is the counting variant of $NP$. As pointed out by @D.W., the problem you picked just so happens to be in $P$, but if you had picked some other problem (such as ...

3

Any decidable problem can be solved by a deterministic algorithm. The thing about SAT (and any other NP-complete problem) is that we don't know any efficient deterministic algorithm that solves it, and we think there might not even be one.

3

It is not true that it requires a non-deterministic algorithm. You are right; if it is solvable, it should be solvable by a deterministic algorithm. And it is. This deterministic algorithm needs exponential number of steps (with respect to number of propositional variables $n$) because only known general case approach so far is to test all combinations of ...

3

This is a situation where coding is non-trivial. $\mathcal{C}_T$ is a class of decidable languages. To make sense of $\mathcal{C}_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it. So what does it mean for $\mathcal{C}_T$ to be recursively enumerable? ...

3

The certificate is a coloring of the vertices into red and blue (i.e., a partition into two sets). Given such a certificate, you can iterate through all the edges and count the number of edges whose endpoints have different colors. This count you can compare against $k$ and answer accordingly YES or NO.

3

This is not a problem. You have an infinite tape, so you can store whatever you want on it. Depending on how explicit your proof should be, consider a few edge cases for defining your transition function: a.) How does your TM recognize, if all n 1s are gone? The complexity of this depends on the alphabet of the TM, if $|\Sigma| > 2$ it should be easy, ...

3

Your problem is in NP. Generalized Sudoku is NP-Complete, but your mapper is in P. Check whether given grid is generated by mapper runs in $\mathcal O(n^2)$ time. Your mapper is not NP-Complete and your decision problem is not NP-hard. On the other hand decision version of Sudoku is NP-hard. The main problem is that you have not provided anything about ...

3

As Konstantin Vladimirov said in the comment: Consider you have this program. Take any while-program and put any instruction 1000 times just before halt. Next run your program and ask if this instruction will be reached 1000 times. Bingo, halting is solved.

3

The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this? First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has ...

2

Suppose that $A,B$ are two DFAs on a common alphabet $\Sigma$ with states $Q_A,Q_B$, initial states $q_{0A},q_{0B}$, final states $F_A,F_B$, and transition functions $\delta_A,\delta_B$. We define a product DFA as follows: $Q = Q_A \times Q_B$. $q_0 = \langle q_{0A}, q_{0B} \rangle$. $F$ consists of all pairs $(q_A,q_B)$ such that either $q_A \in F_A$ and \$...

2

No, the steps are insufficient. You need to use a Karp reduction, since that's the type of reduction used in the definition of coNP-completeness. SAT is NP-complete, but probably not coNP-complete (unless NP=coNP); and coSAT is coNP-complete, but probably not NP-complete. This distinction would be lost if you used Cook reductions. Some questions on this ...

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