New answers tagged

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.


1

A "language" is a set of words over a finite alphabet $\Sigma$ to define a language we have to make an extra step. Take the following definitions s $$L_0 = \{\}$$ $$L_1 = \Sigma$$ $$L_{n+1} = \{(c, w) \mid c \in \Sigma \land w \in L_n\}$$ Note that $(c, w)$ is usually denoted simply as $cw$ or $c \cdot w$ but for the sake of not introducing notation I chose ...


1

It means for every context free language there is an algorithm that can correctly decide if any string S is in the language or not. We can actually say something a lot stronger: There is actually a known algorithm that can take an arbitrary context free language and a string as input and decide in polynomial time whether the string is in the language.


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.


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.


0

A proof of "yes" instance means providing a solution. Providing a solution is providing a valid input. By definition, it can be verified in time and space polynomial relatively to the input, or else it is not a problem in NP. It is unknown whether all proofs of "no" instances are verifiable in polynomial time and space (the difference between NP and Co-NP)....


1

The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input. Given that a Turing machine head moves right one step at a time, a Turing machine head can only read a polynomial amount of the proof in polynomial time. While you could define proofs to exceed a polynomial length, only a ...


1

Thanks to comments by Yuval Filmus, I understand that my question does not make sense as Karp reductions are defined for decision problems. Since Cook reductions allow more freeness, it makes sense to talk about a Cook reduction from a decision problem to an optimization problem, but this is not true for Karp reduction.


Top 50 recent answers are included