14

If by convert you mean reduce (through a Karp-reduction), then it is possible to reduce any problem $A$ in $P$ to any non-trivial problem $B$ in $P$. Here "non trivial" means that $B$ has at least one yes instance $I_Y$ and at least one no instance $I_N$ (i.e., the language associated to $B$ is not $\emptyset$ nor $\Sigma^*$). To map an instance $I_A$ of $...


6

There are a few examples in the answer to Natural complete problems in higher levels of the W-hierarchy. In particular, the W[3]-complete problem $p$-HYPERGRAPH-(NON)-DOMINATING-SET may be useful for your proof. Given that the linked question is now almost 6 years old, you'd perhaps expect some more examples to pop up by now. However, I couldn't find ...


4

Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.


4

$P/poly$ is NOT a subset of $RE$. Specifically, the unary non-halting problem (i.e. given a Turing Machine encoded in unary, does it run forever?) is in $P/poly$ but not $RE$. In fact, every undecidable unary language is in $P/poly$.


4

Your misunderstanding is the meaning of parallelize. In this context, an algorithm can be parallelized if using polynomially many processors, you can compute the answer (in this case, the value of some cell) in polylogarithmic time. Simulating the Game of Life naively takes time proportional to the number of steps. P-completeness of the Game of Life means ...


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


3

$P \subseteq RP $, $BPP \subseteq PSPACE $. So $PSPACE \subseteq P $, $-->$ $BPP \subseteq RP $.


3

Consider the "singleton" languages: $L=\{w\}$ for some fixed word $w$. (e.g., the language $L=\{00010100\}$ would be a singleton language) Most "nice" complexity classes include the singleton languages. Every language can be written as an infinite union of singleton languages. So, if all singleton languages are in the class, and if the class is closed ...


3

Amplification is equivalent to "stretch", the number of (seemingly) random bits that your algorithm generates given the truly random seed. Let $G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a PRG that maps strings of length $n$ to strings of length $l(n)$, then $l(n)$ is said to be the stretch function of $G$. If $l(n)>n$ and $l$ is injective, then you ...


3

First and foremost, I would advise having another look at the basic definitions. An FPT instance is identified by a string $x$ and an integer $k$ such that $(x, k)$ is a yes-instance. Put briefly, if $f(k)$ is not polynomial in terms of $n$ and still depends on $n$, then you cannot obtain an FPT algorithm. We require that $k$ is fixed, or independent of $n$...


2

Let $f(n) = n^{\log n}$. Then $\mathsf{P} \subseteq \mathsf{DTIME}(f(n))$ while $\mathsf{DTIME}(f(2n+1)^3) \subseteq \mathsf{EXP}$. (Actually, whether this argument works depends on the exact definition of $\mathsf{DTIME}$. If it doesn't, take $f_C(n) = Cn^{\log n}$ and sum over all integer $C>0$.)


2

Your problem is #P-hard. Indeed, given a #SAT instance with variables $x_i$ and clauses $C_j$, let $\kappa_{i,b}$ be the product of the clauses $C_j$ satisfied by the truth assignment $x_i=b$, and consider $$ P = \prod_i (\kappa_{i,0} + \kappa_{i,1}). $$ The coefficient of $\prod_j C_j$ in $P$ is the number of satisfying assignments. In the other direction, ...


2

We typically think of instances to problems as being in some format. There are several ways to think of this. Consider for example $A_{TM}$, in which the input is a pair $\langle M,w \rangle$. The three most obvious are: Every input string can be decoded into an input pair $\langle M,w \rangle$. Inputs not of the form $\langle M,w \rangle$ don't belong to ...


2

It has been proven that TSP is $FP^{NP}$-complete but it remains an open question whether TSP is a function problem in $FNP$ (it probably is not). The reason is that, in the case of TSP, the optimal solution is not an adequate certificate, as we do not know how to verify in polynomial time that it is optimal. You can see a proof that TSP is $FP^{NP}$-...


2

The problem is PSPACE-complete. The problem is in PSPACE. You can test whether such a machine halts in polynomial space, by running the Turing machine for $2^n |Q| n + 1$ steps, where $|Q|$ is the size of the finite control, and checking whether it halts. Why? Each configuration of the Turing machine is determined by the values on the tape, the state of ...


2

If you consider $L$ to be a parameter, then yes, you have an FPT time algorithm, and your parameterized problem is indeed in the complexity class FPT, but be precise when you define your problem so that it is indeed stated as a parameterized problem. Although we often refer to things as FPT algorithms, it is actually the problems that are FPT or not. Just ...


2

Let $T_1$ (resp. $T_2$) a polynomial-time probabilistic Turing machine with error probability of at most $1/3$ for $L_1$ (resp. $L_2$). Let $T'_1$ (resp. $T'_2$) be a Turing machine for $L_1$ (resp. $L_2$) obtained by running $T_1$ (resp. $T_2$) $9$ times and returning the majority result. The error probability of $T'_1$ (resp. $T'_2$) is at most $p_F = \...


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

You just need to show that $$ \lim_{n \to \infty} \frac{\log^r n}{n^p} = 0. $$ This is trivial if $r \le 0$ since $\frac{\log^r n}{n^p} = \frac{1}{n^p \log^{-r} n}$ and $\lim_{n \to \infty} n^p \log^{-r} n = +\infty$. For $r>0$, you can use l'Hôpital's rule $\lceil r \rceil$ times to obtain: $$ \lim_{n \to \infty} \frac{\log^r n}{n^p} = \lim_{n \to \...


2

$L\in DTIME\left(2^{n^c}/n^c\right)$ if there exists a machine $M$ running in time $O\left(2^{n^c}/n^c\right)$ which correctly decides membership to $L$ for an infinite number of input lengths, i.e. for every $k\in\mathbb{N}$ there exists $n\ge k$ such that $\forall x\in\{0,1\}^n : M(x)=\mathbb{1}_{x\in L}$. You can think of it as having a non trivial ...


1

I assume $X,Y$ and $Z$ are languages. Now if a language $A$ is polynomial-time reducible to another language $B$ this means there exists a function $f$ that can be computed in $O(n^k)$ such that: $$p\in A \iff f(p) \in B$$ Now if such a function $f_{xy}$ exists for $X$ and $Y$ and such a function $f_{yz}$ for $Y$ and $Z$, you can construct a new function $...


1

It's true: Assume $Y\in NP$. Now let $N$ be the poly time verifier for $Y$. Lets also call the poly time reduction $\phi$. Then, notice that $x\in X\iff\phi(x)\in Y\iff \exists w.N(\phi(x),w)$. Therefore, let us build the poly time verifier for $X$ as follows: $M(x,w):$ Compute $\phi(x)$ in poly time Emulate $N(\phi(x),w)$ and accept if and only if $N$ ...


1

In the definition of SUBEXP, $\epsilon$ ranges over all positive reals. But you get the same definition if you ask that $\epsilon < \epsilon_0$, for an $\epsilon_0>0$ of your choice; if you ask that $\epsilon$ be rational; if you only go over $\epsilon = 1/n$; and so on. This is because DTIME is monotone: if $f \leq g$ then $\mathsf{DTIME}(f) \subseteq ...


1

$AMA$ is basically a 3-round interactive proof system where the verifier (Arthur) is only allowed to send randomness to the prover (Merlin). I haven't seen such an explicit definition yet, but I think we can formulate it as follows. The first round of AM[3] starts with Merlin sending a message $m_1$ to Arthur. In the second round, Arthur sends randomness $r$ ...


1

First, let me note that the question's title is a bit misleading, because $P$ is a subset of $NP$. See also Yuval Filmus's comment. I assume what you intended to ask is whether it's in $P$ or in $NP \setminus P$. Also, the name "DNF" specifically refers to a disjunction of elementary conjunctions, not a disjunction of arbitrary functions. What you ...


1

The fact that the base class can simulate the oracle does not mean that the oracle does not give additional power. Consider the polynomial hierarchy, $\mathsf{NP,NP^{NP},NP^{NP^{NP}}},...$ at the $i$'th level you get an oracle for the $i-1$ level, so following your line of thought we should not gain additional power. However a naive simulation of the oracle ...


1

You seem to be using the following definition of $\mathsf{NP} \cap \mathsf{coNP}$: it consists of all languages of the form $L_1 \cap L_2$, where $L_1 \in \mathsf{NP}$ and $L_2 \in \mathsf{coNP}$. However, in reality $\mathsf{NP} \cap \mathsf{coNP}$ consists of all languages $L$ such that $L \in \mathsf{NP}$ and $L \in \mathsf{coNP}$.


1

Let $U$ be the set of rows in the given matrix and $V$ the set of columns. For each $x$ at row $i$ and column $j$, add an edge between row $i$ and column $j$. You will have an (unweighted) bipartite graph $G=(U,V, E)$. The problem is to find a perfect matching, which is basically the same as find the maximum matching of $G$. There are various algorithms that ...


1

The following survey states that the result is proved by Ibarra, Jiang, Ravikumar in Information Processing Letters (1988). Unambiguous Auxiliary Pushdown Automata and Semi-unbounded Fan-in Circuits. Niedermeier R., Rossmanith, P., Information and Computation 118(2), 227-245, 1995.


1

$C_2 \subseteq NL$: Let $L \in C_2$. Let the log-space verifier for $L$ be $T$. We can construct a log-space NTM $T'$ which on any input simulates $T$ on the same input. Whenever $T$ tries to read the witness-tape, $T'$ just non-deterministically guesses an alphabet. This will have the same effect as having a read-once witness tape.


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