# Tag Info

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

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

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

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

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

7

Wikipedia is describing Levin's universal algorithm. This is an algorithm for verifiable problems, which is competitive with the optimal algorithm (in some sense). In particular, the exact same approach would work for any problem in NP, not just SUBSET-SUM.

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

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

No, it's not an optimization problem. It takes at least one step of computation per bit or word of output (depending on the model of computation), so since the output can be $\Omega(2^N)$, that means the worst-case running time will be $\Omega(2^N)$, no matter what algorithm you use. Thus, the complexity is $\Omega(2^N)$. Yes, the size of the output is a ...

3

Checking whether the number of nonzero elements on each row is at most $2$ can be done in $O(1)$ space on a row-by-row basis by simply counting those elements. Therefore the only interesting part is checking the condition over the columns. This can be done in $O(M)$ space by keeping a counter for each column. In details, the counter $c_i \in \{0,1,2\}$ ...

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

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

Assuming $P\not=NP$ there are lots of problems incomparable with $SAT$, hence neither $NP$ nor $NP$-hard. Here's an overkill generalization of this fact: Suppose $X\not\in P$. Then there is some $Y$ such that $Y$ is incomparable with $X$ under polynomial-time-Turing reducibility (hence a fortiori Karp reducibility). (So in particular if $P\not=NP$ we ...

2

As confirmed independently in another answer, 2P2N-3SAT is already NP-complete. Another name for the fragment you are interested in is (3, B$k$)-SAT where "B" stands for Balanced and indicates that there are the same number of positive and negative occurences of the variables, $k$ is the number of positive and the number of negative occurences, and the 3 ...

2

Nice question. Notations and terms $M$ or $N$ means a Turing machine (TM), whose specification may or may not given. $\langle M\rangle$ is the description of $M$ according to a predefined effective encoding scheme for TMs. $L(M)$ is the language recognized by $M$, i.e., the set of words accepted by $M$. At least that is what I have seen everywhere. ...

2

I'm not an expert, and I have one blank space in my answer, hope someone might fill it in. $FBPP$ is the class of search problems $R = (B_x)_{x\in\{0,1\}^*}$ for which there exists a probabilistic polynomial-time algorithm $A$ that, given $\langle x, 0^ {1/\varepsilon}\rangle$ as input, produces an output $y$ such that $Pr [y \in B_x] ≥ 1 − \varepsilon$,...

2

The complement (note spelling) of $\mathrm{SAT}$ is the set of all binary strings that do not encode a satisfiable Boolean formula. That is all strings that encode unsatisfiable formulas, and also any strings that don't encode any formula at all. In practice, we tend to ignore strings that don't encode a valid input to the problem. For any sane encoding, ...

2

Yes. Every computation problem can be viewed as computing a function $f:\{0,1\}^ \to \{0,1\}^*$: on input $x$, the algorithm outputs $f(x)$. Here is a corresponding decision problem: given $x$ and $i$, determine whether the $i$th bit of $f(x)$ is 1. If you can solve that decision problem, you can solve the original computation problem. (Strictly speaking,...

2

Disclaimer This solution assumes that the language $\text{Acyclic}$ is the language that contains exactly all acyclic directed graphs. It is impossible to achieve this in polynomial time unless $\operatorname{P}=\operatorname{NP}$. The reason is that the problem you have to solve is NP-hard. It is called the directed feedback arc set problem. It is one of ...

2

In short, the greedy algorithm works, where in each step you find the largest number in $A$ and subtract it from $b$. If $b$ becomes zero, you get a solution. If you reach a point where all numbers in $A$ are greater than $b$ output no. In the following I list a formal description of the algorithm and a proof of correctness. Here is a formal description of ...

2

Here is a reduction from the Hamiltonian path. Given a graph $G=(V,E)$. Add a vertex $v_0$ to the graph and connect it to all vertices in the graph. Set $t(v_0)=2$. Set $t(u) = 1$ for all $u \neq v_0$. Claim. The previous reduction is correct. Try to prove it formally as an exercise. Edit. Here is a brief proof of correctness. We have to prove that the ...

2

Concretely, we are always dealing with syntactical transformations, regardless whether there is a semantic theory that renders these transformations intelligible to us, or not. In the end, our ability to automatically demonstrate that two different programs are equivalent is restricted to properties that can be defined syntactically. Even then, there are ...

2

Your problem is decidable. If $M$ always executes less than 5 steps, then it never sees more than the first 4 symbols of its input. Hence it suffices to run $M$ on all inputs of length at most 4.

2

If a you are given a palindrome $p$ of size $N$ (as you say in the beginning of the question), then the longest palindrome is $p$ itself and you don't need to do any computation. If your input is not a palindrome but an arbitrary string, then you need to at least read the input and therefore $\Omega(N)$ is a trivial lower bound.

2

No, and the example you list is a classic example: as far as we know, factoring does not appear to be in $P$, but determining whether a number is prime is definitely in $P$. Another example: Consider the game Hex. Consider the decision problem: given $n$, determine whether the first player has a winning strategy for Hex on a $n \times n$ board. There is a ...

2

This is hard as the integer factoring problem (simply take $N$ to be 2 or a random prime that has no factor in common with $M$). Whether there is a polynomial-time algorithm for factoring is a famous open problem, but it is widely believed that there likely is no such algorithm.

1

Regarding the specific problem you pose about whether the bit of a number can be permuted to give a prime, I believe the following to be an algorithm in P. If the number has fewer than 100 zeros in it or fewer than 100 ones in it, enumerate all permutations and test them all for primality using a primality test (e.g. AKS) and output accordingly. Otherwise ...

1

Let us take as an example MAX CUT. The optimization problem is: given a graph $G$, find the value of the maximum cut. The decision problem is: given a graph $G$ and an integer $k$, determine whether there is a cut of value at least $k$. If we can solve the optimization problem, then we can solve the decision problem: just compare the value of the maximum ...

1

NP doesn’t look at how hard it is to find a certificate (in this case a factor), just at how hard it is to test a certificate that claims to prove the answer is “yes”. So it doesn’t matter how hard it is to find a factor, just that given a factor of an n-bit number, you can easily verify that it is a factor in $O(n^2)$. Or a bit faster with more effort. So ...

1

Problem A is in NP if: B is in NP and you can reduce B to A in polynomial time -> B $\leq_p$ A Not quite right. The class P is a subset of NP anyway, and hence A is already NP if it is in P. The question is whether A is in P or not. By reducing B to A in polynomial time, you prove that any polynomial solution of A is a polynomial solution of B. ...

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