Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
3,599
questions
0
votes
0answers
4 views
Minimization of superlinear functions
Let $A\in\mathbb N_+$, and let $f:\mathbb N_+\to\mathbb N_+$ be non-decreasing function that satisfies $f(n)\in \Omega(n)$ .
Is it true that
$\displaystyle\min_{a\in\{1,\dots,A\}}\{f(a)+f(A-a)\}=f\...
0
votes
1answer
19 views
Showing that $BPP \subseteq EXP$?
I am trying to understand why $BPP \subseteq EXP$. This question almost gives the answer (simulate $BPP$ machine on all possible toin cosses and then "act accordingly"). However, it is not clear to me ...
0
votes
2answers
40 views
An example of a computable problem that is not in P
I am trying to find a simple example of a problem that is computable but not in P, I know very well that it would be enough to get one in NEXTIME-complete however the problems that I find in this set ...
-2
votes
1answer
20 views
Question about complexity of TSP Optimization problem
Is this statement true?
Optimization TSP problems are known to be NP-hard, as we do not have a minimum cost to compare against, and in order to verify a solution is optimal, we need to iterate ...
1
vote
1answer
30 views
Injectivity verification in o(n) space and O(n) time
The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to ...
1
vote
1answer
20 views
Question about proof of $NTIME(n) \subseteq DTIME(n^{1.2})$ implies $\Sigma_2-TIME(n^{8}) \subseteq NTIME(n^{9.6})$
In "Computational Complexity, A modern approach", Arora & Barak proof the following claim (Claim 5.11.2):
Suppose that $NTIME(n) \subseteq DTIME(n^{1.2})$. Then $\Sigma_2TIME(n^{8}) \subseteq ...
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
45 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
94 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
17 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
23 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
25 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
18 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
17 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
31 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
84 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
47 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
145 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
45 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
50 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
40 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
21 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
424 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 ...
