Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
3,593
questions
1
vote
0answers
20 views
Why can KARP reductions be used to define completeness for complexity classes in the polynomial hierachy?
When defining $\Sigma_i^P$ or $\Pi_i^P$ completeness, we want to use a reduction that fulfills the following property:
If $L' \leq_p L$ and $L \in \Sigma_i^P$ or $\Pi_i^P$ respectively, then $L'$ is ...
0
votes
0answers
36 views
What's the proof complexity of E-KRHyper (E-hyper tableau calculus)?
Before the question, let me explain better what is E-KRHyper:
E-KRHyper is a theorem proving and model generation system for first-order logic with equality. It is an implementation of the E-hyper ...
-1
votes
0answers
15 views
Promise problems in $NP$?
Is there a good examples of promise problems in $NP$, $coNP$ and $NP\cap coNP$?
2
votes
3answers
92 views
Is the P vs NP problem, an NP or co-NP problem?
A few years ago, a youtube channel named hackerdashery, made an extraordinary youtube video explaining P vs NP, in a semi-vulgarized way :
https://www.youtube.com/watch?v=YX40hbAHx3s
At 7 minutes ...
1
vote
0answers
15 views
Deterministic Time Hierachy Proof by Arora and Barak: Question about time to simulate Turing Machine $M$ that decides separating language
In the book "Computational Complexity: A modern approach", Arora and Barak proof the statement that $DTIME(n) \subsetneq DTIME(n^{1.5})$ by constructing a separating language $L \in DTIME(n^{1.5})$ ...
0
votes
1answer
23 views
Can you determinize an NFA in PSPACE?
QUESTION
Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$?
MORE DETAILS
I'm asking this as I want to be able to ...
2
votes
1answer
394 views
Halting problem in EXP-complete
I have some troubles understanding why the halting problem is in EXP.
In Wikipedia the following is written:
It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is ...
0
votes
1answer
22 views
A doubt on converting NOT gate to CNF formula
For a NOT gate if $x_1$ is input and $x_2$ is the corresponding output, I see the equivalent CNF (conjunctive normal form) is $(x_1 \lor x_2) \land (\overline x_1 \lor \overline x_2)$.
My ...
1
vote
0answers
17 views
Which is harder, an NP-complete problem or the Raz-Tal oracle problem?
This is a (hopefully) sharper version of a question that I asked previously.
Which of these algorithms is believed to have a longer asymptotic runtime?
The optimal algorithm guaranteed to solve some ...
1
vote
0answers
14 views
Do relativized relations between complexity classes tell us anything about the nonrelativized relation?
The existence of relativized relations between complexity classes seems to often be treated as "circumstantial" evidence about the "true" or "real-world" (i.e. nonrelativized) relation between the ...
1
vote
1answer
10 views
Hardness of approximation statement clarification?
In the paper I'm reading, there is a hardness of approximation result for an algorithm proved using a reduction to set cover. Roughly, the claim states that if there existed an algorithm that solved ...
0
votes
0answers
27 views
Algorithm and Time Complexity for k-Sum problems
In fact, there are three different k-Sum problems:
Problem1: Given unsorted integer array $\{a_1, a_2, ..., a_n\}$ and a target number $T$, determine whether there exist at least one solution $\{a_{...
0
votes
0answers
22 views
Non intersecting paths of graphs with obstacle number one
There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
1
vote
1answer
17 views
Differences between ALLTM and INF
The definitions of ALLTM and INF are as follows:
$$\mathrm{ALLTM} = \{ \langle M \rangle \mid \text{ TM $M$ such that $L(M) = \Sigma^*$} \}. $$
$$\mathrm{INF} = \{ \langle M \rangle \mid \text{...
0
votes
0answers
8 views
Un-compute an operator given its oracle access
In general, is it easy to un-compute an operator given its oracle access? I want to ask in terms of computational complexity, that is, if there's any computationally feasible way to do this, or if not,...
1
vote
1answer
17 views
Hamiltonian non intersecting path in plane
$N$ points are located in 2D plane. Some of the pair of the points are connected by line segments. What is the complexity of the problem of existence of Hamiltonian non intersecting path? What if we ...
2
votes
0answers
16 views
Does Cook and Ruzzo's result also hold for logspace-uniform AC0?
In Cook's famous paper on $\mathsf{NC}$, he cites the following result:
PROPOSITION 4.7 (Cook and Ruzzo, 1983). $\mathsf{AC}^k$ consists of those
problems solvable by uniform unbounded fan-in ...
1
vote
2answers
30 views
Complement of languages and coNP
By definition, any language (decision problem) $L$ is defined as a subset of $\{0,1\}^*$, where $\{0,1\}$ is the alphabet.
$L^c$ is said to be the complement of the language, and it seems to be ...
1
vote
0answers
39 views
Why is IP important? [closed]
Why is the complexity class IP important?
What additional insights does this class give us that we could not get from NP or RP?
4
votes
0answers
83 views
The relationship between matrix inversion, the HHL algorithm, and the unlikely scenario that $BQP = PSPACE$
I am studying the quantum computing algorithm presented in the paper Quantum algorithm for linear systems of equations}.
Without going through all the details, the HHL algorithm is able to apply an ...
1
vote
1answer
48 views
1
vote
0answers
37 views
How does the number of clause affect the difficulty of a 3-SAT Problem? [closed]
It was asked here and closed although it is a very specific question witch was exactly answered in several papers. The complexity of 3-SAT problems has a phase transition which reaches the critical ...
0
votes
0answers
7 views
Wrong proof of coNL=NL [duplicate]
Given the st-connectivity problem (we need to decide if there is a directed path from s to t in a graph G: https://en.wikipedia.org/wiki/St-connectivity) we have a non-deterministic Turing machine M ...
0
votes
1answer
28 views
Subset Sum to SAT reduction
I have seen numerous ways to reduce CNF-SAT to SS, but is there any way to reduce SS to SAT (or one of its variations)? I have tried researching it, but all it brings up is the (apparently) much more ...
0
votes
1answer
24 views
TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not?
So this is a question pertaining to the proof for $PSPACE-COMPLETE$ (for TQBF for example). The idea is to first prove the $L$ $is$ $PSPACE$(easy part) and next is to prove $PSPACE-COMPLETE$. The ...
-2
votes
1answer
111 views
PH=PSPACE implies collapse of PH? [closed]
If PH=PSPACE, does this imply that the PH collapses to one of its levels?
(somehow I get an error message when posting "question doesn't meet quality standard" so I add this sentence in order to ...
0
votes
0answers
46 views
What is the complexity class of exponential parallelism?
Consider the class of problems that can be computed when you have access to exponentially many processors working in parallel.
How does one capture that in a proper formalism? Is there some ...
2
votes
1answer
44 views
runtime of 2 dependent nested for loops [duplicate]
for (i=1; i<=n ;i=i*2){
for (j=1; j<=i ;j++){
basic_step;
}
}
Regarding the above nested loops, I can't seem to understand why is the following ...
-1
votes
2answers
140 views
The Halting problem proof is wrong?
First, let's see the pseudocode proof of halting problem:
P(x) =
run H(x, x)
if H(x, x) answers "yes"
loop forever
else
halt
Then we have a ...
0
votes
1answer
41 views
Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem
We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says:
Let $L\in NPSPACE$.
Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that ...
0
votes
0answers
30 views
Logarithmic reduction from Clique to Half-Clique
so the question is in the title basically but I am now studying for a Complexity Theory Exam and encountered this problem in the exercises.
I understand how to make a poly-reduction but I am not able ...
0
votes
3answers
61 views
Is there a unit of measurement that can express code execution speed in absolute terms?
I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware ...
2
votes
1answer
68 views
Polynomials - using Newton's method, or not?
I have to find a root of polynomial of degree $n\ge2$. I need to write code to calculate the root for different values of $n$. Only 1 real positive solution is needed.
I can use general Newton's ...
3
votes
1answer
48 views
Basic complexity theory (in Oracle Separation of BQP and PH)
I have some basic questions about complexity theory that came up when I tried to understand the result by Raz and Tal that BQP$^O\nsubseteq$ PH$^O$.
Aaronsons paper was helpful, but I still have some ...
2
votes
1answer
39 views
If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case?
According to this source,
If A is reduced to B and A ∈ class X, then B cannot be easier than X. This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to ...
0
votes
0answers
7 views
Oracle separation between AWPP and QMA
Are there any known oracle separations between AWPP (defined in http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf) and QMA (the quantum analogue of MA)?
0
votes
0answers
22 views
What does W1 and W2-hardness imply?
Is there any simple definition to understand W1-hardness $\&$ W2- hardness in complexity theory? What I understood, that is the following: Let $\Pi$ be a decision problem with parameter $k$, then $...
1
vote
1answer
18 views
Polysize bounded depth circuit for modified MAJORITY problem
I am trying to show the existence of a polynomial size, bounded depth monotone circuit on the inputs $(x_1,\ldots, x_n)$ that gives $1$ if $\sum x_i \geq n/2 + n/\log n$ and $0$ if $\sum x_i \leq n/2 -...
0
votes
0answers
15 views
Relationship between IP, IPS, IPP and NP
I read these notes which mention IPS (Interactive proof system) https://people.csail.mit.edu/ronitt/COURSE/S12/handouts/lec6.pdf
I then saw IPP being mentioned in complexity zoo: https://...
-1
votes
3answers
423 views
One-way Trapdoor Function
Do the functions of the collatz conjecture and their inverses model a Trapdoor Function?
If given a, b, a^-1, b^-1 and your choice of f(x), is it “hard in the average case” to find some secret x?
I ...
0
votes
1answer
55 views
Is every Turing complete set for EXPSPACE autoreducible?
I'm reading about autoreducibility, which is the following notion:
A set $L$ is autoreducible
if there is a polynomial-time oracle Turing machine $M$
that accepts $L$ using $L$ as an oracle, ...
0
votes
3answers
78 views
How Reduction works in proving NP-Hard?
A problem $X$ is $NP$-Hard if for all $Y \in NP$, $Y \leq_P X$. Further, if a problem $Z$ is $NP$-Complete, and $Z \leq_P X$, then I can prove (rather mechanically) that $X$ is $NP$-Hard.
I also ...
0
votes
0answers
6 views
maximize Steiner vertices in graphs of diameter 3
Let $G=(V, E)$ be a simple connected graph of diameter 3 and $T \subseteq V$ be a set of terminal vertices in $G$. For any $T' \subseteq T$, $(V', E')$ denotes a subgraph of $G$ containing $T',$ ...
1
vote
1answer
39 views
Why is $ZPP \geq BPP$ not true?
This seems like a silly question, but I couldn't find a conclusive answer for it.
As far as I know, ZPP contains algorithms which run in polynomial time and either return a known-correct answer or ...
1
vote
2answers
48 views
Why are Oracle Separations Counted as Evidence toward Unconditional Separation?
Particularly, we already have some oracle separation results such as $\mathbf{BPP}^A\neq \mathbf{BQP}^A$ [Simon], $\mathbf{NP}^A\not\subseteq \mathbf{BQP}^A$ [BBBV], and $\mathbf{BQP}^A\not\subseteq \...
1
vote
1answer
35 views
Complexity of K-Colorful Coloring Problem for a Hypergraph
I searched a lot trying to find a reference for the complexity of K-colorful coloring problem for a hypergraph but I cannot find it. Please if anyone has a reference for the complexity of the problem ...
0
votes
0answers
33 views
Is the language $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$ decidable?
I have stumbled upon this language: $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$. At first, it looked like an undecidable problem, but I have failed to prove it, and now ...
2
votes
2answers
54 views
Decidable Program Equivalence
Determining whether two programs always return same output for same input is undecidable (easily reduced to the halting problem). My question is, is there a complexity class in which this problem is ...
3
votes
1answer
60 views
how to solve simultaneous equation with O(n)
Does someone know how to solve the below?
Assume that the array $A$ is already sorted.
And show an $O(n)$-time algorithm that determines whether or not there exist indices $i,j,k$ such that
$A[i] + ...
1
vote
1answer
26 views
Diagonalization argument for MAJORITY
For any language $A$, define a language $L_{A}$ as:
$L_{A} = \{0^{n}: \text{Number of strings in $A$ of length $n$ is more than $2^{n-1}$} \}$
I am trying to construct an $A$ such that $L_{A} \notin ...
