7

Your problem is not in P, for two different reasons: P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP. The output could be exponentially large in the input length: encoding $b$ takes about $\log b$ bits, but encoding $a^b$ takes about $b \log a$ bits. This still ...


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


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


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


2

Chess is a fixed, finite problem. Because there's no input, you can solve it in a constant amount of time. Computational complexity considers problems with inputs and looks at how the cost of the computation increases as the input gets longer. For example, you could generalize chess from an $8\times 8$ board to an arbitrary $n\times n$ board and ask how the ...


2

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


2

Savitch's theorem implies that NPSPACE is equal to PSPACE, and so it is closed under polynomial time reductions.


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

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


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

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

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

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.


1

Suppose you have a (randomized) verifier $V$ such that, for all $Q,w$, $$\begin{align*} w\in L &\implies \Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3\\ w\notin L &\implies \Pr[V\leftrightarrow Q\text{ accepts }w]= 0. \end{align*}$$ Since $P$ is one possible value of $Q$, it follows that $$w\notin L \implies \Pr[V\leftrightarrow P\text{ accepts }...


1

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


1

For interested readers, here are some of related definitions. A function $f : \Bbb N \to\Bbb N$ is a proper complexity function if $f$ is nondecreasing and there is a $k$-string TM Mf with input and output such that on any input $x$, $M_f(x) = \sqcap^{f(|x|)}$ where $u$ is a tally (“quasi-blank”) symbol, $M_f$ halts within $O(|x|+f(|x|))$ ...


1

Hardness is often intuitively explained as a lower bound. In general, "hardness results" obtained by reductions yield a conditional lower bound that relies on assuming a sort of lower bound on a single problem. In the case of NP-hardness, the following statement is true: assuming P$\neq$NP, NP-hard problems cannot be solved in polynomial time P$\neq$NP ...


1

Yes, if P = NP then any decision problem is NP hard as long as there is one problem instance where the answer is "YES" and one where the answer is "NO". Just check the definition of NP-hard (and check why problems where every instance has the answer YES or every instance has the answer NO are not NP-hard by that definition).


1

This question is very natural since most if not all common functions that appear in the runtime-analysis of algorithms form a totally ordered set in terms of little $o$-notation or big $\Omega$-notation such as shown in this answer by Robert S. Barnes or this answer by Kelalaka. However, there is no such totally-ordered set of representative functions for ...


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