Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

Filter by
Sorted by
Tagged with
-2
votes
0answers
16 views

I want to know the complexity of this following code [closed]

include include include void main() { char p[10][5],temp[5]; int i,j,pt[10],wt[10],totwt=0,pr[10],temp1,n; float avgwt; printf("Enter no of girls:"); scanf("%d",&n); for(i=0;ipr[j]) { temp1=pr[...
1
vote
1answer
16 views

Consequences of the Time Hierarchy Theorem

The form of the Time Hierarchy Theorem that I have is this: If $f$ is time constructible then $\text{DTIME}(f(n)) \subsetneq \text{DTIME}(f(2n+1)^3)$. We want the consequences of this to be that $\...
3
votes
1answer
40 views

Is there a complexity class QPP?

The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach ...
1
vote
1answer
34 views

Oracle query’s required

The variables $a,b,c \in \{0,1\}$, thus $a^k, b^k, c^k \in \{0,1\}$ I want to pass a query to an oracle that returns the coefficients of each term $(1,a,b,c,ab,ac,bc,abc)$ in the expansion of ...
1
vote
1answer
33 views

Is $L \subset 1NL$ when $L \neq NL$? [closed]

A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
0
votes
0answers
37 views

What is at least weakly NP-hard problem?

It is known that some problem P is at least weakly NP-hard. What does at least part of the statement mean? Is it possible that problem P is strongly NP-hard? Is this a stronger, i.e. more precise, ...
12
votes
1answer
183 views

Are there any known AM-complete problems/is AM-complete well defined?

I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not ...
0
votes
0answers
16 views

Prove that a set is decidable using time constructible function

I'm preparing an exam of theory of computation and I'm very in trouble with some exercise. Considering a Turing machine $\mu$ of alphabet $A=\{ 0,1 \}$ (we don't know nothing about termination) and a ...
8
votes
3answers
4k views

Do any decision problems exist outside NP and NP-Hard?

This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a ...
1
vote
0answers
82 views

Class of languages recognizable by n-bit formulas of size at most $T(n)$

A Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies: fan-in=2 for the AND and OR nodes fan-n=1 for the NOT nodes fan-...
1
vote
1answer
61 views

The padding argument in the proof of NTIME(n) ⊆ DTIME(n^1.2) implies Σ2-TIME(n^8) ⊆ NTIME(n^9.6)

In "Computational Complexity, A modern approach", Arora & Barak proof the following claim (Claim 5.11.2): Suppose that $\mathsf{NTIME}(n) \subseteq \mathsf{DTIME}(n^{1.2})$. Then $\Sigma_2$-$\...
2
votes
0answers
61 views

Proving a pattern exist in a string without revealing where

Some time ago i read the following problem (i don't remember the article from which i read it from) : "Suppose you are given a picture where the goal is to find waldo (from the game where is waldo), ...
3
votes
1answer
80 views

Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$ and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $. I´ve made a program to check this statement and it ...
0
votes
0answers
21 views

Proof by padding: $\textsf{TIME}(t_1(n)) = \textsf{TIME}(t_2(n)) \implies \textsf{TIME}(t_1(f(n))) = \textsf{TIME}(t_2(f(n)))$

I've been given the task of proving the statement in the title, which I found out it should be called the translational lemma by means of a padding argument; $f$, $t_1$ and $t_2$ are three ...
0
votes
1answer
31 views

how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then ${NP = P ? }$
6
votes
1answer
145 views

Have any natural complexity classes been proven not to be closed under complement?

Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be? I'm sure one could construct some contrived ...
3
votes
1answer
125 views

CIRCUITSAT ∈ DTIME(2^n/n^c) ⟹ NP ≠ EXP?

$\mathsf{EXP}\not\subseteq \mathsf{DTIME}(2^{n})$ and $\mathrm{CIRCUITSAT}\in \mathsf{DTIME}({2^{n}})$ holds and so why does $\mathsf{NP}\neq \mathsf{EXP}$ not hold while we know $\mathsf{NP}\subseteq ...
5
votes
1answer
127 views

If NP is a subset of DTIME[n^O(log n)] then what happens?

If $\mathsf{NP}\subseteq \mathsf{DTIME}[n^{O(\log n)}]$ then what happens? Does it imply $\mathsf{NP}\neq \mathsf{EXP}$? Is there any other consequences such as $\mathsf{BPP}\neq \mathsf{EXP}$? Does ...
2
votes
1answer
73 views

Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)

I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time ...
0
votes
1answer
316 views

Modular exponentiation running time

I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student). Is it poly ...
3
votes
1answer
102 views

What is the consequence of $\oplus P\neq PP$?

From $P\subseteq \oplus P \subseteq PSPACE$ and $P\subseteq PP \subseteq PSPACE$ we infer $\oplus P\neq PP$ gives that $$P\neq PSPACE.$$ Are there any other consequences?
262
votes
7answers
122k views

What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
1
vote
0answers
34 views

Complexity problem reduction?

Let say A and B are two decesion problems where A $\le$ B polinomial reduction is true. Is this : A̅ $\le$ B̅ also true? If so, can you show an exemple, if not why?
0
votes
1answer
84 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 ...
5
votes
2answers
80 views

Does $P/O(1)$ equal to $P$ if solver needs to consider smaller inputs?

Suppose that $F$ is a problem such that for every $n$, there is a program of length $O(1)$, running in polynomial time to $n$, that solves $F$ correctly on all instances of size less than $n$. Can $F$ ...
8
votes
1answer
200 views

is $P_{CTC} = BPP_{path}$?

I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic. This is my reasoning, and I would like to know if (1) this is ...
3
votes
1answer
101 views

Grover's algorithm on probabilistic classical machines

As a starting point for this question, I came across this question, which AIUI is citing a construction showing how to simulate quantum circuits with a $PP$ algorithm, i.e. implying quantum ...
0
votes
0answers
31 views

A heuristic for finding an edge cycle cover

I am looking to find a minimum list of cycles in a graph such that their union gives the list of all simple cycles in this graph. In the example below, here are 4 simple undirected cycles: 1-2-3, 2-3-...
3
votes
0answers
40 views

Approximate algorithms for class P problems

As a part of my Algorithm course we studied Approximate Algorithms for NP-complete or NP-hard problems, e.g. "set cover", "vertex cover", "load balancing", etc. My professor asked us as an extra ...
0
votes
0answers
30 views

Cook Levin Theorem (Sipser Proof) (phi move)

In Sipser's proof of the cook levin Theorem the move function (phi move) checks whether a given window is legal. For that we must have an exhaustive set of all possible legal windows to verify that a ...
0
votes
0answers
35 views

Why is $DSPACE(\log(n)) = NSPACE(\log(n))$ not known?

Here $DSPACE(\log(n))$ is the family of algorithms for which there exists a deterministic Turing machine using $O(\log(n))$ space. On the other hand $NSPACE(\log(n))$ is the family of algorithms for ...
1
vote
1answer
76 views

If a sparse language is NP-complete then are all NP languages sparse?

If a Sparse Language is NP-complete then are all NP languages sparse? We say a language is sparse if $\forall n \in \mathbb{N}, |L \cap \{ 0,1 \} ^{n}| \leq p(n)$, for some polynomial $p(n)$?
0
votes
1answer
56 views

If a sparse language is NP complete, then are all languages in NP in P/poly?

If a Sparse Language is NP complete, then are all languages in NP in P/poly? I know that sparse languages are in P/poly, but does a polynomial time reduction give an addition to the circuit that is ...
-1
votes
1answer
55 views

A simple clarification on polynomial hierarchy

$P^{NP}\subseteq BPP^{NP}$ holds. According to current knowledge $BPP$ is in $\Sigma_2^P\cap\Pi_2^P$ holds. So according to current knowledge is following true? $P^{\Sigma_2^P\cup\Pi_2^P}\subseteq ...
2
votes
1answer
69 views

{0,1}* ∈ P class?

I have the following question about complexity time classes. Given the language $L = \{0,1\}^*$, is it inside the class P or not? $$ L = \{0,1\}^∗ ∈ P? $$
1
vote
1answer
58 views

If an NP complete problem 'A' is polynomial time reducible to another problem 'B' does that imply 'B' is also NP complete?

The following question was asked on a quiz: Let S be an NP-complete problem, and Q and R be two other problems (that we don't know much about). If we now know that Q is polynomial time reducible (i....
5
votes
1answer
362 views

Is every PSPACE-complete problem complete with respect to logspace reductions?

A remarkable feature of the reduction showing that TQBF (True Quantified Boolean Formulas) is PSPACE-complete is that it actually runs in logspace, i.e. for any $A \in \mathsf{PSPACE}$, $$ A \le_L ...
1
vote
1answer
81 views

Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction. According to these posts : Why not polynomial-space ...
5
votes
0answers
101 views

Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?

I have read that minimizing regular expressions is, in general, PSPACE-complete. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P? The language ...
0
votes
2answers
186 views

Reducing from NPC to Co-NPC => NP = Co-NP?

In my lecture we learned: If X is NPC and X in Co-NP => NP = Co-NP Would it be enough to prove NP = Co-NP if I reduce a ...
4
votes
1answer
324 views

Oracle Turing Machine EXP^EXP

I'm reading Arora Barak and in that it is written that when $O \in \mathrm{P}$, then $\mathrm{P}^O = \mathrm{P}$. Can this be generalized? Intuitively, I think that $\mathrm{NP}^\mathrm{NP} \neq \...
1
vote
1answer
90 views

Does EXP^EXP = EXP? [duplicate]

Does $\mathrm{EXP}^\mathrm{EXP}=\mathrm{EXP}$? Here is my thought: $\mathrm{EXP}$ machine can ask $2^{O(n)}$ queries to the oracle, and each oracle would itself solve an exponential time problem in a ...
4
votes
1answer
330 views

Is DISCRETE LOG a NP hard problem?

In cryptography there are two problems which are part of the foundation of modern public key cryptography. Both of them can be solved in polynomial time on quantum computers. I am talking about: FACT ...
10
votes
5answers
14k views

Are all Integer Linear Programming problems NP-Hard?

As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming ...
2
votes
1answer
37 views

On the robustness of BQP class

Typically the notion of quantum Turing machine is introduced with its transition function. $$ \delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}} $$ Where $\mathbb{C}'\...
2
votes
2answers
174 views

Big-O Notation and Calculus?

I was wondering if there are any calculus relationships implicit in Big-O notation. For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
1
vote
0answers
23 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
0answers
119 views

Proving that $BPP^{BPP}=BPP$ [duplicate]

I'm trying to prove that $BPP^{BPP}=BPP$. $BPP\subseteq BPP^{BPP}$ is obvious. I'm struggling with $BPP^{BPP}\subseteq BPP$.. Can anyone help?
1
vote
1answer
39 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 ...

1
2 3 4 5
7