# Tag Info

5

The issue is that your proposed algorithm is polynomial with respect to the numerical value of the input, but not relative to the input's size. The binary encoding of $N$ requires at most $\lceil\log n\rceil$ bits, so an algorithm which takes the encoding of $N$ and preforms $\Omega(N)$ operations is actually exponential. Such algorithms are said to run in ...

5

I know that NP-complete problems cannot be solved in polynomial time. We don't know this. This is exactly the P vs NP question. NP-complete problems can be solved in polynomial time iff P=NP. If P ≠ NP, then all problems in NP cannot be solved in polynomial time. P is a subset of NP, so some problems in NP can definitely be solved in polynomial time. ...

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

4

The main problem with your argument is that guessing a completely unknown password doesn't fit in the framework of P vs NP. P and NP are classes of decision problems. This means that you are given an input and you have to answer "yes" or "no". For example, in the Hamiltonian graph problem you are given a graph and you answer either "...

4

A decision tree is a model of computation which makes sense for instance of constant size. In contrast, a language is usually a collection of instances of unbounded size. An automaton (in this context) is a model of computation which describes a language. The upshot of all this is that in most circumstances, it doesn't really make sense to convert a decision ...

3

A decision problem has a yes/no answer, so it can't have "exponential size". You are asking about search problems, those can certainly have exponential size. And yes, if the size of the solution (written down in some suitably compact format, that is) is exponential in the size of the original problem, it is clearly impossible to even write down the ...

3

This answers a different version of the question, in which the language in question is $L(A) \setminus L(B)$. Here is an algorithm for deciding $L$: Use the product construction to construct a DFA $C$ whose language is $L(A) \setminus L(B)$. Let $D$ be a DFA whose language is $0^*1^*$. Use the product construction again to construct a DFA $E$ whose language ...

3

There are at least two ways to do it. The first is to take a disjoint sum of $B$ and $C$, which can be done in many ways, for example $$\{0x : x \in B\} \cup \{1y : y \in C\}.$$ The second is to use an NP-complete language $L$ as an oracle. Since any problem in NP reduces to $L$ in polynomial time, you can simulate a $B$-oracle using an $L$-oracle.

3

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.

3

Every language that is in NP is by definition decidable. Becase if a language L is in NP, than there is a nondeterministic Turing Machine that decides it in polynomial time, and thus L is decidable.

3

Let $I$ be your instance and consider the instance $I'$ obtained by replacing each bit vector $y$ in $L_1$ with $y' = y \oplus S$ (where $\oplus$ denotes bitwise xor). Call $L'_1$ the list containing all vectors $y'$. Consider the tuples $(x_1, x_2, \dots, x_l)$ and $(x'_1, x_2, \dots, x_l)$ where $x_i \in L_i$ and $x'_1 \in L'_1$. We have: $$x_1 \... 3 Maybe I should summarize what I was saying in the comments. Yes, the problem should be formulated precisely in order to give an answer. About the cases in which the answer is NO: For those formulations in which the answer is NO it is usually for a trivial reason. For example, one case that is mildly interesting is if we are considering the polynomials with ... 3 In complexity theory, we often concentrate on decision problems. "Officially," NP-hardness is a category of decision problems — only a decision problem can be (or not be) NP-hard. However, it is also common to use NP-hardness when referring to optimization problems. An optimization problem is NP-hard if its decision version is NP-hard. In more ... 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 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 In fact, if L_1 is regular then L_1/L_2 is regular for any L_2. Indeed, consider a DFA for L_1 with transition function \delta and accepting states F. We modify the set of accepting states to$$ F' = \{ q : \delta(q,w) \in F \text{ for some } w \in L_2 \}. $$You might object that "F' cannot be computed". So what? We never said that you can ... 2 This is the hitting set problem in disguise. Let U=\cup_{A_i \in \mathcal{C}} A_i be the universe and \overline{X} = U \setminus X. Then your problem can be equivalently stated as follows: given \mathcal{C} and k, find \overline{X} that has |U|-k elements, and such that A_i \cap \overline{X} \ne \emptyset for each A_i \in \mathcal{C}. That ... 2 What you are really asking is whether given automata A,B, we can construct an automaton whose language is the left quotient$$ L(A) \backslash L(B) = \{ w : \exists x \in \Sigma^* \text{ s.t. } x \in L(A) \text{ and } xw \in L(B) \}. $$(The question has meanwhile changed to refer to right quotient, which can be handled similarly.) Here is such a ... 2 The phrase Every context-free language is decidable has the following meaning: If the language L is context-free, then L is decidable or in other words If L is a context-free language then L is a decidable language 2 You don't have to verify that V' is minimum. The decision version of Vertex Cover (which you have quoted in your question) only asks you to decide whether there is a vertex cover of size at most k. To verify that V' is a valid yes-certificate for an instance \langle G=(V,E), k \rangle you just check that: V' \subseteq V, |V'| \le k, and \forall ... 2 The certificate you propose might not be polynomial in the size of the input. The input size of the problem is O(n^3 + \log k), while your certificate has size \Omega(k \log n). This is not polynomial, e.g., for k = 2^n. Your certificate would work if you set it, e.g., to an empty list whenever k = \Omega(\frac{n^2}{\log n}), and modify the verifier ... 2 There is a finite number of different states (the set of values of the variables and the program counter). Your "limited goto programs" are just a (messy) way to describe a deterministic finite automaton. Or just reason that the program states being finite, it is certainly possible to map out all possible non-looping computations (by something like ... 2 Your language L_1 = \{\langle M\rangle \mid \emptyset \subseteq L(M)\} is trivially decidable by a Turing machine T that just checks whether \langle M \rangle is a valid description of a Turing Machine. If it is, T accepts. Otherwise T rejects. Notice that, for any Turing machine M, L(M) is a set (by definition) and therefore \emptyset \... 2 In this particular example, the following works: Let A be the algorithm for deciding whether some graph G has a TSP-route has a cost of at most b. We start by finding the optimal b^\ast using A and binary search on an appropriate range (say [0, \sum_{e \in E(G)} w(e)]) in polynomial time. Following this, we start modifying the instance graph G ... 2 The proof in theorem 1 in [Liberatore'02] shows that irredundancy is NP-hard by reducing SAT to it. Considering any set of non-tautological clauses \Gamma=\{\gamma_1,\dots,\gamma_m\} (think of this as the set of clauses of a CNF boolean formula), it builds in polytime a set of clauses \Pi_\Gamma which is irrendundant iff \Gamma is satisfiable (again, \... 2 Let \phi = C_1 \lor \cdots \lor C_m be an instance of SAT, where all clauses are non-empty, and m \geq 2. We create a new CNF \psi whose clauses are$$ z_1 \lor C_1, \ldots, z_m \lor C_m, z_1 \lor \cdots \lor z_m,  where $z_1,\ldots,z_m$ are new variables. Then $\phi$ is satisfiable iff $\psi$ is irredundant. Suppose first that $\phi$ is ...

2

Note that when $k$ is a fixed constant (that is, $k$ is not part of the input, for example $k = 17$ ), then the problem is easy. Indeed, in this case, your suggestion works because $n \choose l$ is polynomial in $n$, for every $l\leq k$. Also, checking whether a graph is bipartite can be done in polynomial time. If $k$ is part of the input, then your problem ...

2

As you suggested, think how to reduce from the halting problem $Halt_{TM} = \{ \langle M, w\rangle: \text{$M$halts on$w$} \}$. On input $\langle M, w\rangle$, the reduction should output a pair of TMs $\langle K_1, K_2\rangle$; such that $M$ halts on $w$ iff $L(K_1) = L(K_2)$. This is somehow a basic reduction that can be done by standard tricks, so it ...

2

I suspect that the question is looking for a non necessarily tight lower bound to the number of comparisons needed. The decision tree needs to be able to return the correct sorted sequence no matter what the initial permutation of the elements is. Therefore, it must have at least $n!$ leaves (one for each output permutation). Each internal vertex in the ...

1

A word $w$ belongs to $L_5$ if for all $x \in \{0,1\}^*$ it is the case that $M_w(w) = x$. In particular, if $w \in L_5$ then $M_w(w) = 0$ and $M_w(w) = 1$, which can't both be true. So no word belongs to $L_5$.

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