New answers tagged complexity-theory
1
Under the assumption that $NP\neq \mathrm{co}NP$, we have that:
$$P^{SAT[1]}=NP\cup \mathrm{co}NP\implies P^{NP[1]}\neq P^{NP[2]}$$
Proof: Since $D^p\subseteq P^{NP[2]}$, we deduce that $(SAT\dot{\land} UNSAT)\in P^{NP[2]}$.
Meanwhile, $(SAT\dot{\land}UNSAT)\notin NP$ due to $UNSAT\notin NP$ and similarly, $(SAT\dot{\land}UNSAT)\notin \mathrm{co}NP$ due ...
4
From the definition you gave, the supersets have to be removed, as you want to keep only those sets for which there is no proper subset in $\mathcal{F}$.
For example:
In blue are the sets of $\mathcal{F}$ which don't have proper subsets in $\mathcal{F}$, in red are the ones who do. You want to keep the blue ones, by definition of $\pi$.
2
You problem is solved trivially in order statistic trees, where each node has an additional size attribute, and many answers have already mentioned this situation.
So what to do first is to calculate and memorize size for each node ($O(|V|)$), and then do a BST search to find the node with rank $|V|/2$, which is $O(\log(|V|))$ for balanced trees.
This ...
3
A $\mathsf{BPP}$ machine $A$ has randomness complexity $r(n)$ which is polynomial in $n$. Hence, an $\mathsf{EXP}$ machine $B$ can loop over all $2^{r(n)}$ values of the random tape of $A$, simulating $A$ with each random input (each simulation taking polynomial time), and count how many times $A$ accepts or rejects. The overall decision of $A$, then, is ...
0
This statement seems quite vague and confused.
NP-hardness is precisely defined, and you shouldn't loosely say "optimization TSP problems" because it doesn't specify the problem(s). In fact, it is not uncommon that seemingly small changes in a problem lead to different complexities.
Further, because NP-hardness is precisely defined, a problem is not NP-...
3
As Yuval Filmus already mentioned in the comments, because of the time hierarchy theorem, we know $\mathsf{P} \neq \mathsf{EXP}$. Hence, any $\mathsf{EXP}$-complete problem is an example. These include, for instance, generalized chess and checkers.
1
This isn't really a natural example, but a natural technique (which I'm leaving as an answer instead of a comment since I think it's still valuable, and it's clearly too long): we can use a diagonal argument. Specifically, while we can't tell whether a Turing machine runs in polynomial time, we can whip up a list of polynomial-time Turing machines such that ...
0
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$ ...
2
You haven't specified your exact computation model, so let me assume that you measure space in words of length $\Theta(\log n)$, and that each element in the array occupies one word. Let me assume furthermore that you can compare two elements in constant time.
The oracle should provide you with the relative order of the elements, say as an array $B$ whose ...
0
Theorem-proving is co-NP-complete :
Depending on the underlying logic, the problem of deciding the validity of a formula varies from trivial to impossible. For the frequent case of propositional logic, the problem is decidable but co-NP-complete, ...
- https://en.wikipedia.org/wiki/Automated_theorem_proving
In a comment, Yuval Filmus did state that ...
0
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 ...
3
There are grave conceptual issues at hand here.
Establishing proofs is the aim of mathematics. This is a task carried out by humans, usually using pen (or pencil) and paper. Some amount of coffee might be involved in the process too. This definitely has nothing to do with $\mathsf{NP}$.
Now, "proofs" may be meant in the sense of logic and proof systems. ...
5
It isn't meaningful to say that a single specific question is in NP or any other complexity class. In order to classify things as being in P, or NP, or co-NP, etc. they need to be sets of problems with some parameter. So for example, the problem "Is the positive integer n prime" is a question where we can discuss this sort of thing.
In a certain overly ...
0
The subset construction can be computed (and negated) in polynomial space. Remember that the output doesn't count as part of the space usage in bounded space computation.
Determinization can exponentially increase the number of states: the language of $0$–$1$strings such that the $k$th-from-last character is $0$ can be recognized by an NFA with ...
4
You are referring to the following problem:
$$H = \{ (\langle M \rangle, w, t) \mid \text{$M$ accepts $w$ in time at most $t$} \}$$
where $t$ is binary encoded. You should note this is not the (classical) halting problem, but, rather, the bounded version of the halting problem. The halting problem itself cannot be complete for $\mathsf{EXP}$ (or any other ...
0
Your formula does actually look like $x_2 = F(x_1)$, it's just written with different symbols.
First, we can rewrite the two clauses using implication. Since $(a \to b) \iff (\neg a \lor b)$, we can rewrite the formula as
$$
(\neg x_1 \to x_2) \land (x_2 \to\neg x_1)
$$
Now, you can recognize that this is $(a \to b) \land (b \to a)$, which is to say $a \...
0
No, there are a special kind of integer program, if the constraint matrix is TUM (totally unimodular matrix), then it can be relaxed into the linear program, which can be solved in polynomial time.
0
Since $1 + \log n = (1 + o(1)) \log n$, for every $\beta < \alpha$ you can find $N$ such that for $n \geq N$,
$$ (1-\alpha)(1 + \log n) \leq (1-\beta) \log n. $$
This suffices to reach a contradiction.
1
The two sets are clearly different – there are Turing machines whose language is infinite but doesn't consist of everything. However, both languages belong to the same Turing degree, that is, each of them can be reduced to the other (computably).
Given an instance $M$ of ALLTM, construct a Turing machine $M'$ which on input $x$ runs $M$ on all inputs $y \...
1
Hamiltonian path problem remains NP-complete in planar graphs [1], so your problem is also NP-complete since in a planar graph, two edges cannot intersect with each other.
[1] Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1976). The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4), 704-714.
2
The complement (note spelling) of $\mathrm{SAT}$ is the set of all binary strings that do not encode a satisfiable Boolean formula. That is all strings that encode unsatisfiable formulas, and also any strings that don't encode any formula at all.
In practice, we tend to ignore strings that don't encode a valid input to the problem. For any sane encoding, ...
1
As I understand it, you are interpreting the space $\{ 0,1 \}^\ast$ to be the (disjoint) union of $F$ and $\overline{F}$, where $F$ is the set of valid formulas and $\overline{F}$ is the set of strings which do not encode a formula (according to some unspecified encoding). Then, in your perspective, we should have that $F = \textsf{SAT} \cup \overline{\...
2
At best, the evidence given is only heuristic and informal, but it is still important. Oracles in the examples you gave do address the general question: how does quantum computing compare to nondeterminism and randomness, in power? The oracles definitely do not answer the original unrelativized questions, rather they provide a different (related) black-box ...
1
The meaning of $O(n^2)$
I was told that the complexity of bubble sort is $O(n^2)$. But when I run with a reversed list (worst case) with size 3, the counter finishes with the value 12, shouldn't it be 9?
Had $O(n^2)$ meant $n^2$, we should have written it as $n^2$ instead of that funny looking $O(n^2)$. Instead, $O(n^2)$ means no more than $n^2$ roughly. ...
0
Your evaluation only works into one direction, you can use it to test for unsatisfiability for the listed cases which are only a subset of all unsatisfiability cases.
Imagine for example a formula in which 100 clauses contain x and one clause contains (¬x ∨ ¬x ∨ ¬x).
1
You can reduce addition to a circuit with XOR, AND, OR gates.
Each element of the sum must first be ANDed with an extra variable that is true if the element belongs to the subset, and false otherwise.
Then the circuit can be trivially reduced to 3-SAT. The clauses are determined by the gates.
For example each AND gate (A & B = C) requires these 4 ...
1
In the proof of the $\textit{PSPACE-}$completeness of TQBF, we need to construct a formula of some specific type. The recursive midpoint algorithm is easy to implement (and Savitch's Theorem requires finding the $\textit{algorithm}$), while the same idea, if performed in a similar manner, results in an exponential formula (and the completeness proof requires ...
2
yes, it says so on wikipedia https://en.wikipedia.org/wiki/Polynomial_hierarchy
"If the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. Since there are PSPACE-complete problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse"
6
You are committing a logical error. This question has nothing whatsoever to do with computability and machines. It is entirely about how to prove that something does not exist. Namely, to show the statement
$$\lnot \exists x . \phi(x)$$
we do as follows:
Assume that there is $x$ such that $\phi(x)$. We assume this even though perhaps we have no idea how to ...
Top 50 recent answers are included
