New answers tagged complexity-theory
1
an $NC^0$ can only consider circuits of fan-in 2. If we try to adding with a Full-Adder with Lookahead Gatter to calculate the carry, needs every Full-Adder 3 Input signals. But in $NC^0$ are only 2 inputs allowed.
If we try to replace Full-Adder with other logic gatters, we hurt the depth of the circuit.
image-source: https://upload.wikimedia.org/...
0
Your reasoning seems correct, but you are missing a crucial step once the second bullet point is done with: You check that your problem is also complete for the class $C$ you have found for it. For instance, if you have a problem $P$ and show it is reducible to a complete problem in $\mathsf{PP}$, then you are not done yet. For all we know, $P$ could be $\...
0
Your reasoning is essentially correct. Assuming your TMs are deciders (i.e., they must also properly reject their inputs), you don't even need an extra step in your algorithm; you can just swap the accept and reject states of your TM (just like you do with DFAs!).
In case your TMs are only defined as acceptors (i.e., a word not in the language will not ...
1
If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1)
First of all we do not know any exponential or sub-exponential time algorithm that requires only $O(1)$ space, having said this, it is difficult to reason about a hypothetical algorithm "A" because the spatial and temporal complexity are closely ...
1
Morioka considers uniform versions of his circuit classes:
Throughout this paper we write $\mathbf{NC^1}$ to mean $\mathbf{Dlogtime}$-uniform $\mathbf{NC^1}$, which is equivalent to the class $\mathbf{Alogtime}$ of languages accepted by an alternating Turing machine in $O(\log n)$ time.
The paper you mention should imply the equivalence of these two ...
1
The Immerman–Szelepcsényi theorem states that $\mathsf{NSPACE}(s(n))$ is closed under complementation whenever $s(n) \geq \log n$.
3
A nondeterministic Turing machine can guess at most one bit each step — this is how they are defined. In particular, a nondeterministic Turing machine running in constant time can be converted to a deterministic machine also running in constant time. This should allow you to answer your own question.
0
NP-hardness is a category that applies to both decision problems and optimization problems. In contrast, NP-completeness is a category that applies only to decision problems.
Here are the relevant definitions:
A decision problem is in NP if it is accepted by some polynomial time nondeterministic Turing machine.
A decision problem is NP-hard if all problems ...
0
Suppose that there exists an integer $K$ and a polynomial time algorithm $A$ which, when run on a graph $G$, outputs a value $A(G)$ which satisfies
$$
|A(G) - \alpha(G)| \leq K,
$$
where $\alpha(G)$ is the maximum size of an independent set in $G$.
We will show that $A$ can be used to determine $\alpha(G)$ in polynomial time, which contradicts the ...
-3
Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement,[8] because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse ...
2
If the running time of the algorithm is bounded, in the sense that for every input $x$ there is a number $T(x)$ such that whatever the coin tosses are, the algorithm always terminates within $T(x)$ steps, then you can always "try all possibilities" and convert your randomized algorithm to a deterministic one, albeit with a possibly much larger running time.
...
0
This is basically a maybe more succinct version of gansher729's answer.
A language $L$ is in $\mathsf{NP}$ if for any input $x \in L$, you can find a witness, of polynomial in $|x|$ size, that can be checked in polynomial time. This is, "$x \in L$! Here is a proof, that you can verify in polynomial time."
A language $L$ is in $\mathsf{P}$ if for any input $...
1
If we look at decision problems, then a problem is in P if for "YES" instances "I think the answer is YES" is a witness that can be checked in polynomial time :-)
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 "...
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.
...
2
In an $\mathsf{NC^0}$ circuit, every output bit depends on a bounded number of input bits. But the $k$th bit of the output (counting from the LSB) depends on the first $k$th bits of each input.
To see that $\mathsf{AC^0}$ circuits can compute addition, we need to produce such a circuit. Hopefully you have seen such circuits, and otherwise perhaps you can ...
9
Yes. Here's a sketch of a direct proof.
If a problem is in $\mathrm{NP}$, there is a nondeterministic Turing machine $M$ that decides it, and there's a polynomial $p$ such that none of $M$'s computation paths on inputs of length $n$ take more than $p(n)$ steps. That means that a single path can't use more than $p(n)$ tape cells, so we can ...
2
The term or tag you are looking for is "undecidability" or "computability". The basic version of the theory of undecidability is a part of the theory of computation, which is an ingredient of the curriculum of all students majoring in Compute Science, as far as I know.
You can search for "undecidability" or "halting problem", the most famous and the most ...
26
Generally speaking, the following is true for any algorithm:
Suppose $A$ is an algorithm that runs in $f(n)$ time. Then $A$ could not take more than $f(n)$ space, since writing $f(n)$ bits requires $f(n)$ time.
Suppose $A$ is an algorithm that requires $f(n)$ space. Then in $2^{f(n)}$ time, $A$ can visit each of its different states, therefore can gain ...
0
What do you want to say about $a'$ and $b'$? They can't possibly be the same algorithm unless $A=B$, since one of them solves $A$ and the other one doesn't. Even if $A=B$, they're not necessarily the same algorithm: if there's one algorithm that solves some problem, there are infinitely many (your favourite algorithm; count to two and then do your ...
1
how can I relate these two concepts to conclude that inverting a matrix is in $\mathrm{P}$?
You can't. Your question contains two category errors.
Complexity classes are classes of problems, not classes of algorithms. The complexity of a problem is the minimum amount of resources that are required to solve that problem, by any algorithm. "Resources" might ...
3
[...] the structure formerly known as the Polynomial Hierarchy collapses to the level above $\text{P}=\text{NP}$.
This claim makes no sense. If $\text{P}=\text{NP}$, then the whole polynomial hierarchy is equal to $\text{P}$ and there is no level above that.
That is, we show that $\text{co-NP}\subseteq\text{NP}\setminus{P}$.
$\text{co-NP}\subseteq\...
4
I believe the claim is more commonly written as $coNP \subseteq NP/poly$, but that of course does not immediately answer your question.
The fact that this implies that the polynomial hierarchy collapses is shown in Theorem 2 here:
Chee-Keng Yap. Some consequences of non-uniform conditions on uniform
classes. Theoretical Computer Science, 26:287–300, 1983....
1
Gaussian elimination is an algorithm, you can’t frame it as a problem and thus it can’t be in $P$.
But matrix inversion itself is a problem and its decision version is as follows: “does matrix $M$ have an inverse?”
Gaussian elimination then is one possible way to prove that you can always answer that question in polynomial time, therefore matrix inversion ...
2
A reduction can be thought of a way to "rephrase" a problem in terms
of another. This can be denoted using $A \to B$, $A$ reduces to
$B$. This means that if you have an algorithm that solves $B$
then you also have an algorithm that solves $A$, since $A$ reduces
to $B$, $A \to B$. Now you also have $B \to A$ so in some way, your
problems are equivalent since ...
3
Very rarely we measure the exact running times, and when we do, it's specified quite clearly.
Then, there is the big-O notation and its friends, which give information about the asymptotic behavior of the algorithm.
But different big-O sets (being pedant here, O(n) is actually a set of functions) can be grouped into classes. There are linear algorithms, ...
1
Combine the following two facts:
$\mathsf{NTIME}(n) \subseteq \mathsf{TIME}(2^{O(n)})$, by deterministic simulation of nondeterminism.
$\mathsf{TIME}(2^{O(n)}) \subsetneq \mathsf{TIME}(2^{n^2})$, by the time hierarchy theorem.
0
Unfortunately, when you tried to ask a general question to get hints for your homework exercise rather than the solution, you turned the question into something too general to answer. I'll try to come back at some point and write something more useful, now that you've made the question more specific. Diagonalization is the usual technique, similar to how the ...
3
Let's choose $n=2^k$, and see if $T(n)=\lceil\log_2 n \rceil !$ is bounded by a "polynomial of $2^k$" i.e. is $O(2^{mk})$ for some constant $m$. That is, $O({(2^m)}^k)$ for some $m$, or equivalently $O(b^k)$ for some basis $b>1$. In other words, we want to check if $T(n)=T(2^k)$ is bounded by some exponential of $k$.
We have
$$
T(2^k) =
\lceil\log_2 2^k ...
8
Don't trust plots.
By Stirling's approximation (and dropping the ceilings to avoid notational overload),
$$\begin{align*}
(\log n)! &\sim \sqrt{2\pi \log n}\left(\frac{\log n}{e}\right)^{\log n}\\
&= \sqrt{2\pi \log n}\, e^{(\log\log n - 1)\log n}\\
&= \sqrt{2\pi \log n}\, n^{\log\log n - 1}\,,
\end{align*}$$
which grows faster than any ...
0
Hint : Construct a poly-time verifier for L1^C by using L2's verifier, in addition to running some polynomial-time checks.
2
No, this would contradict the time hierarchy theorem. Note that any language in $\mathsf{EXP}$ is polynomial time reducible to some language in $\mathsf{E}$ by padding. Suppose $L\in \mathsf{DTIME\big(2^{n^c}\big)}$, then consider $L'=\big\{x0^{|x|^c}\big|x \in L\big\}$. Obviously $L'\in \mathsf{E}$ and $L\le_p L'$, thus if $\mathsf{E}$ is closed under ...
2
Let USTCON2 be the following problem: given a graph $G$ and two vertices $s,t$, decide whether there is a walk from $s$ to $t$ of even length. Let us show first that USTCON2 reduces to co2COL.
Given a graph $G = (V,E)$ and two vertices $s,t$, construct a new graph whose vertex set consists of two copies of $V$. For every $(a,b) \in E$, connect $a$ in the ...
2
Suppose that $L_1 \in \mathsf{P}$ and $L_2$ is non-trivial. Pick $y \in L_2$ and $z \notin L_2$ arbitrary. The following is a polynomial time reduction from $L_1$ to $L_2$:
Input: $x$.
Check whether $x \in L_1$.
If so, output $y$.
Otherwise, output $z$.
This runs in polynomial time since $L_1 \in \mathsf{P}$.
3
Typically, yes, it's a matter of finding a known NP-complete problem that's somehow similar to the one you're trying to work with. So if you're dealing with a problem about formulas, you probably want to reduce some version of SAT or 3SAT to it.
For graph problems, you probably want to reduce some other graph problem. Problems about long paths and cycles ...
1
The undirected version of PATH, usually known as USTCON, is in L due to Reingold's theorem.
USTCON is trivially complete for L with respect to logspace reductions. I don't know if it is L-complete with respect to weaker reductions such as $\mathsf{AC}^0$ reductions; see this question.
3
Random-access machines support the following operation in constant time:
$$
x \gets M[y],
$$
where $M$ is the memory array, and $y$ is an index whose allowable size depends on the exact model. Whether $M$ is an array of bits or an array of words depends on your exact model.
If you had several different memory arrays, say $M_1[y],\ldots,M_r[y]$, then you ...
0
The other day I was reading a paper on parallelized random access machines without bit operations, which sounded very much like what you are describing. For these models NC is known not to equal P. See here: https://epubs.siam.org/doi/10.1137/S0097539794282930
The paper can also be found on Professor Mulmuley’s website.
0
Show that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$, and so the polynomial hierarchy collapses to NP.
How do you prove that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$?
There are two options:
Show that coSAT reduces to HALFCYCLE. Since HALFCYCLE is NP-complete, in particular it is in NP, and so coSAT is in NP, implying ...
1
In general, each $NP$-hard problem can be reduced to all other known $NP$-hard problems (there exist hundreds).
For the subset-sum there is for a example knapsack. Subsetsum is a specialisation of knapsack.
The other way, if you could solve subset-sum in poly-time, then you would also be able to solve PARTITION (and 3-PARTITION and 4-PARTITION)
4
How to calculate Big O of $T(n) = aT(n^b) + f(n)$ with $0<b<1$?
The powerful technique you are searching for is variable substitution.
Let $S(m)=T(2^m)$. Then
$$S(m)=T(2^m)=aT(2^{mb}) + f(2^m)=aS(mb)+g(m),$$
where $g(m)=f(2^m)$.
Now that we have a recurrence relation about $S(m)$, to which we might be able to apply the master's theorem. Here are ...
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 ...
0
The claim
It follows that, $\forall \Pi,\Pi' \in NP$, if $\Pi'$ is strongly NP-complete, and $\Pi' \leq_{pp} \Pi$, then $\Pi$ is strongly NP-complete.
is wrong (at least for how "pseudo-polynomically reducible" is defined here).
If $\Pi'$ is strongly $NP$-complete, then ``pseudo-polynomially reducible'' is equivalent to polynomially reducible.
Recall ...
3
7 is the least number of questions that you can ask to guarantee to find the treasure.
the idea of binary search
Every time when we ask a question, we try to reduce the maximum number of unit squares left to search as small as possible. That is, try to cut the number as nearly to a half as possible. This is the idea as binary search.
the binary search on ...
0
There is already an answer addressing the NTM definition of $\mathbf{NP}$, so let me address the equivalent definition based on proof systems. (For a proof, check your favorite computational complexity textbook.)
$\mathbf{P}$ is the class of problems solvable by a TM in polynomial time (in the length of the input). $\mathbf{NP}$ is the class of problems ...
1
Clique is the decision version of Maximum Clique, which is an optimization problem:
Clique: Given a graph $G$ and an integer $k$, decide whether there is a $k$-clique in $G$.
Maximum Clique: Given a graph $G$, find the maximum size of a clique.
Let me mention that these names are not standard. Other people might use Clique or Maximum Clique to refer to ...
4
We can assume without loss of generality that the vertex set is $1,\ldots,n$.
Let us say that a vertex is minimal if it has the minimal value in its connected component. You can check that a vertex in minimal in NL by checking that it is not connected to any smaller vertex.
A graph has at least $k$ connected components iff there is a list $v_1 < v_2 < ...
3
A Turing machine is a computation model in theory only, able to simulate any computer algorithm. By formally defining this model, Its possible to draw conclusion and limits regarding the abilities of our computers.
There are many more models, and much more literature about each of them, but below is a short review of the three mentioned in your question
...
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'...
2
It is conjectured that the complexity of SAT on $n$ variables is $\tilde\Omega(2^n)$ (a version of this is SETH, the strong exponential time hypothesis). In contrast, Grover's algorithm solves it in $\tilde O(2^{n/2})$.
On the other hand, it is conjectured that quantum computers cannot solve NP-hard problems in polynomial time, that is $\mathsf{NP} \not\...
Top 50 recent answers are included
