Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
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

Recursive Bubble Sort Complexity

I have this code for a recursive bubble sort: ...
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 ...