New answers tagged complexity-theory
2
votes
Ackermann Decision Problem
No, you don’t need to compute the Ackerman function to verify this at all.
The problem is trivial for x <= 3. And for x >= 4, if you can write down y, then the answer is “no”.
- 27.1k
3
votes
I would like to know what are the directions to work on if I want to prove that $NP=coNP$?
There are no directions that are likely to be accessible to an amateur. The problem is believed to be extremely hard. No one knows of any directions that are believed to be very promising. Instead, ...
D.W.♦
- 150k
1
vote
Accepted
The extent of NP-Completeness
Yes and no, even if we assume P $\not=$ NP was not proven. It depends on how someone "solved" the traveling salesman problem.
If someone constructed a polynomial-time algorithm that solves ...
- 37.3k
2
votes
Accepted
Complexity of this variant of $⊕2SAT$?
This problem can be solved easily: trivially, the number of solutions is 0, so the parity is even.
Consider any other variable $b$. Then because the formula $\varphi$ must contain all clauses that ...
D.W.♦
- 150k
2
votes
Accepted
Non rigorous argument that $P \ne NP$ implies $avgP \ne distNP$
Let $X$ be the chosen subset of inputs to which we can restrict 3-SAT such that algorithm A remains superpolynomial.
Then no algorithm A’ that solves 3-SAT’ can run in polynomial time on average
...
- 7,258
3
votes
Accepted
If $NP^{NP} = NP$, then the polynomial hierarchy collapses to it's first level. How to prove it?
Prove that $\Sigma_i^P = NP$ for $i \ge 2$ by induction on $i$.
The base case is $i=2$ and is trivial since, by hypothesis, $\Sigma_2^P = NP^{NP} = NP$. For the inductive step, suppose that $\Sigma_i^...
- 26k
1
vote
Accepted
Subquadratic multiplication of polynomials in the max-plus/tropical semiring
The problem is computing the array $C$ defined as $C_i = \max_{j+k=i} (A_j + B_k)$ given arrays $A$ and $B$. It is called the max-plus convolution, or MaxConv problem. Note that the equivalent min-...
- 2,175
1
vote
3-Dimensional Matching $\leq$ $_{p}$ subset sum Explanation
When you want to prove a reduction is true (such as this from 3-Dimensional Matching to Subset Sum), what you want to show is that you can take any input for 3-Dimensional Matching and turn it into an ...
- 682
2
votes
Is maximal independent set on maximal planar graphs still NP-complete?
This is more of a comment, but I want to append an image. The following graph is maximal planar and every node has degree 4, thus the proposed algorithm does not work. The maximal independent set of ...
- 1,509
0
votes
what are the performance differnces (space and time complexity) between count-min sketch and quotient filter?
Quotient Filter
Time complexity
The quotient filter offers a constant time complexity of O(1) on average with most operations. However, in the worst case, all operations might take logarithmic time ...
- 1
1
vote
Unlimited use subset sum
If the $k_i$ are restricted to be positive integers (please clarify whether this is the case or not in your question), D.W.'s nice approach could give an invalid answer (i.e., an answer with some $k_i$...
- 5,314
2
votes
Unlimited use subset sum
Compute $g = \gcd(z_1,z_2,\dots,z_n)$, where $Z=\{z_1,\dots,z_n\}$. If $g | z$, then you can use the extended Euclidean algorithm to find such a linear combination. Otherwise, there does not exist ...
D.W.♦
- 150k
3
votes
Accepted
Why NP is not certain subset in P/poly?
The problem is that you have to transform the input for the original machine into a unary input for the unary machine. This cannot be done in polynomial time in the size of the original input, ...
- 682
0
votes
Accepted
How to show a language is in NP?
You have already figured out that $f^{-1}(x)$ can be used as a potential NP certificate. You are just missing the crucial part in the definition of NP.
You don't have to compute the certificate, you ...
- 38
0
votes
How to show a language is in NP?
The value $f(x)$ is a polynomial length certificate for the language, since it has the same size as $x$, and can be checked in polynomial time by verifying that $f^{-1}(f(x)) = x$ and that $f(x) < ...
- 213
0
votes
How is the Subset Sum Problem NP-Complete?
The subset sum problem can easily be solved in polynomial time in the number of items, and the sizes of the items. However, to be in NP, the solution must be in polynomial time in the problem size. ...
- 27.1k
2
votes
Are there any other language classes of time complexity between the P language class and the NP language class?
PMar's answer is correct. Having said that, there are several language classes "between" $P$ and $NP$.
An example is $RP$, the class of languages accepted in randomised polynomial time. A ...
- 19.8k
2
votes
Difference between function and search problems?
$\mathrm{PPAD}$ is a class of search problems, not of function problems. The notion of search problem is more general than that of function problem, which in turn is more general than a decision ...
- 2,556
2
votes
Accepted
Is this variant of #Positive 2-SAT #P-complete?
It can be solved in polynomial time, and thus is unlikely to be #P-complete. Every such formula has the form
$$\varphi = \bigwedge_{j=1}^{k} \bigwedge_{i=1}^{a_j-1} (x_i \lor x_{a_j})$$
where $a_1,\...
D.W.♦
- 150k
2
votes
Can a DFA have multiple of the same state?
Ask yourself this: what do you mean by the same state? In particular, why do your two $B$ states need to be the same state and what value does that give you over treating them as two separate states?
...
- 1,219
0
votes
Can a DFA have multiple of the same state?
A DFA must have at most a single transition on a given input. In your example, being in state $B$ and reading a 1 you have two choices for the resulting state: go to $A$ or $C$. You could, though have ...
- 14.7k
Top 50 recent answers are included