A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.
5

No one knows, but: It is suspected that neither factoring nor discrete logarithm are NP-complete, but we have no proof. (Evidence for the suspicion: they are in NP $\cap$ coNP. See, e.g., https://cstheory.stackexchange.com/q/159/5038, https://cstheory.stackexchange.com/q/167/5038 for factoring. It's similarly easy to prove that discrete log is in NP $\...


5

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


4

Because average case requires a definition of "average". Specifically, average over what distribution of inputs? Worst-case does at least give you an objective guarantee: whatever input you consider, it won't be worse than this. That sort of guarantee still has some value even if the worst-case inputs aren't representative of what you're going to be doing. ...


4

P, NP, NP-complete and NP-hard are complexity classes, classifying problems according to the algorithmic complexity for solving them. In short, they're based on three properties: Solvable in polynomial time: Defines decision problems that can be solved by a deterministic Turing machine (DTM) using a polynomial amount of computation time, i.e., its running ...


4

Suppose that $F$ is a problem such that for every $n$, there is a program of length at most $C$, running in polynomial time, that solves $F$ correctly on all instances of size less than $n$. Let $P_n$ be a program of length at most $C$, running in polynomial time, that solves $F$ correctly on all instances of size less than $n$. Since there are only ...


3

A useful exercise to answer the question could be to build a simple Turing machine $M$ (let's say one tape and one head) that recognizes your language. Such a TM could work directly on the input tape and be equipped with an extremely simple transition function: Read input If $($input $= 0$ $\lor$ input $= 1$$)$ $\implies$ Move R (right on the tape) Note ...


3

an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step I don't think that's really true. It seems to me that all you're doing here is observing that a discrete linear function changes by a constant amount at each step and wondering if that's connected to the fact that the derivative of a continuous ...


3

If $\textbf{NP} \subseteq \textbf{DTIME}(n^{O(\log n)})$, then we get $\textbf{P}^\textbf{NP} \subseteq \textbf{P}^{\textbf{DTIME}(n^{O(\log n)})} = \textbf{DTIME}(n^{O (\log n)})$. Continuing this reasoning, the entire polynomial hierarchy $\textbf{PH}$ is contained in $\textbf{DTIME}(n^{O(\log n)})$. By the time hierarchy theorem, $\textbf{DTIME}(n^{O(\log ...


2

There is a polynomial time algorithm that determines whether a system of linear equations over the integers has a solution. The algorithm uses Hermite normal form, which can be computed in polynomial time. See lecture notes of Swastik Kopparty: Hermite normal form and finding integer solutions. Your proof that your problem is in coNP is incomplete, since ...


2

Yes, you can decide this language in logarithmic space, using the following algorithm: for each clause in the CNF: do a linear scan of $w$ to see if one of the literals in the clause is satisfied; if not, reject if you got through all the clauses without rejecting, accept What's the space complexity? Well, there are at most $n$ clauses, so we need at ...


2

A clear explicit relationship is that Big Oh is defined via limits which of course are central to calculus.


2

The accepted answer is incorrect: 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 ...


2

All that you know is that R is NP-hard. To show that R is NP-complete, you need to show that it is in NP. But that is not automatically true. As an example, let S be the question "Is there a path of cost at most l that visits every node of a graph G?" and R be the question, "What is the cheapest path that visits every node of a graph G?" These are ...


2

Let $F$ be a function that maps integers from $0 \dots N-1$ to $\{0, 1\}$. We want to find $x$ (which is promised to be unique) such that: $$F(x) = 1$$ Now let's take two random integers $a$ and $b$ from $0 \dots N-1$ and output: $b$, if $F(a) = 0$ $a$, if $F(a) = 1$ For any fixed $x$ and $y$ we have: $$P_{a=x} = P_{b=x} = P_{a=y} = P_{b=y} = \frac{1}{N}...


2

In order to compare two quantities/expression, it is often easier if they are in the same form. Here try expressing $t_a(n)$ as $2^{s_a(n)}$ and compare $s_a(n)$ with $\sqrt{\log_2 n}$. Additionally, beware of using a program to check asymptotic comparisons: e.g. $f(n)=n^{10^6}$ and $g(n)=(1,0000000000000001)^n$


1

I don't think you're likely to find any such proof. Given our current level of knowledge, as far as we know it is possible that $\textsf{P} \ne \textsf{NP}$ but $\textsf{NP} = \textsf{co-NP}$ (we cannot prove otherwise). If that were true, then we'd have $\textsf{NPC} = \textsf{co-NPC}$ (and thus $\textsf{NPC} \cap \textsf{co-NPC} \ne \emptyset$) yet $\...


1

It is enough to pad a special delimiter (say a comma) and $(|x|^2-|x|-1)$ 1's. Suppose $L_\mathrm{pad}= \left\{\left\langle x,1^{|x|^2-|x|-1} \right\rangle : x \in L\right\}$. Since $L\in\mathsf{DTIME}(2^n)$, there is a TM that can determine whether $x\in L$ in $O(2^{|x|})$ time. We then construct a new TM: given a string $y$, it first checks whether $y$ has ...


1

Yes, see Mahaney's theorem. It states that if a sparse language is $\mathbf{NP}-$complete, then $\mathbf{P=NP}$, and since $\mathbf{P\subseteq P_{poly}}$, then $\mathbf{NP\subseteq P_{poly}}$


1

If we only consider the latter half of the question: "are all NP languages sparse", the answer is no. A counterexample is $\{0,1\}^*$. It belongs to NP but is not sparse. However, you added a precondition: "a sparse language is NP-complete", and $A\rightarrow B$ is true if $A$ is false, so the answer depends on whether there exists a NP-complete sparse ...


1

Your reduction $f$ works in nondeterministic logspace, which is conjectured to be stronger than logspace. Assuming this conjecture, it follows that the concept of NL-completeness is not trivial, that is, not all problems in NL are NL-complete; in particular, problems in L are not NL-complete. What might be confusing you is that PSPACE=NPSPACE, which is ...


1

In short yes Proof Let's assume $X$ is NP-complete and $X$ is in co-NP. We show that $NP \subseteq coNP$ and viceversa. [$NP\subseteq coNP$] Because $X$ is NP-complete $=>$ for each $L\in NP$ we can found a polytime function $f$ that $s\in L$ iff $f(s)\in X$. But $X$ is in coNP $=>$ for the polityme reduction closure of coNP, $L\in coNP$ too $=&...


1

The language $$L_1 = \{(x,u) ~|~ \exists v\in \{0,1\}^{d|x|^8}M(x,u,v) = 0\}$$ belongs to $NTIME(n)$ by design, since $|v| = O(|x| + |u|) = O(|x|^{8})$. By the assumption of the theorem, $L_1$ is decidable by some deterministic $D$ in $O((|x|+|u|)^{1.2}) = O(|x|^{9.6})$ steps. The recipee for $D$ isn't important, but the existence of such algorithm $D$ ...


1

Your definition of EXP is a bit off (you're thinking of $\textbf{E} = \textbf{DTIME}(2^{O(n)})$ instead of $\textbf{EXP} = \textbf{DTIME}(2^{n^{O(1)}})$), but either way the assertion that "each oracle would itself solve an exponential time problem in a single step" is false. This is because, given exponential time, the machine can write (say) $2^n$ bits to ...


1

A strong k-coloring of a hypergraph assigns distinct colors to every member of a hyperedge and uses $k$ colors. When the hypergraph is $k$-uniform, this problem is equivalent to the problem you describe. Further, this problem is NPC as shown by Colbourn, Jungnickel and Rosa [1]. You can also prove yourself that this problem is NPC by a straightforward ...


1

We will show that $A_{TM}$ is complete for your class. In order to show that, we need to show that for every language $A\in L\cup \{A_{TM}\}$, it holds that $A\le_L A_{TM}$. First, if $A=A_{TM}$, then the trivial reduction suffices. That is, a reduction that given input $x$, return $x$. Clearly $x\in A_{TM}\iff x\in A_{TM}$. Now, if $A\in L$, we need to ...


1

This problem is known as maximum matching of a bipartite graph. Basically let vertex $p_i$ (resp., $q_i$) represent the $i$th person (resp., task). And we connect $p_i$ and $q_j$ with an undirected edge iff person $i$ can do task $j$. The answer of the original problem is exactly the maximum matching of the new graph. For algorithms, the classical Hungarian ...


1

If you want to categorize a problem in a way that makes it comparable to other problems, then you need to categorize it the same way as everyone else does. If you are only interested in one particular problem, then you can analyze it any way you like. You might look at the worst case, or the average case, or you can analyze "typical" cases, whatever "...


1

I think here is a pitfall due to inaccurate notation. Notation for me: A trail is a sequence of distinct connected edges. A path is a trail with distinct vertices. In the problem instance $MNPL$ (maximum neighbor path length) the sets $(G,N^+, N^-)$ and the weight function $c_e$ are given as input(and hereby fixed). Since $N$ is partitioned, for two ...


1

Let us reduce REACH to TARGET. Given an instance $(G,s,t)$ of REACH, add edges from all nodes other than $s$ to $s$ to form a new graph $G'$. If $t$ is reachable from $s$ in $G$ then it is reachable from all other nodes in $G'$ using the new edges. Conversely, if $t$ is reachable from all other nodes in $G'$, then in particular it is reachable from $s$ in $G'...


1

After a while I look back on this problem. It turns out using universal gates to generate constant-qubit gates would make no difference to BQP class. The gate complexity, however, depends on $\epsilon$ for the error we try to bound, but precision could be reached in $poly(-\log{\epsilon})$ number of operations.


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