# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

344 questions
Filter by
Sorted by
Tagged with
15 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 ...
78 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-...
64 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 ...
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 ...
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), ...
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 ? }$
65 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 ...
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?
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$ ...
100 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 ...
30 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-...
36 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 ...
29 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 ...
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 ...
48 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 ...
73 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)$?
68 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?$$
53 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....
66 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 ...
168 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 ...
98 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 ...
291 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 ...
58 views

47 views

### Is PSPACE vs NEXPTIME known?

I know that P = PSPACE is a famous open problem, and that EXPTIME = NEXPTIME is also unknown. By the time heirarchy theorem we know that NP is a strict subset of NEXPTIME. Is anything known about ...
26 views

### Problem class of assigning N persons to N tasks, zero costs with prefs

I am looking for the general problem class / computational complexity / algorithms for the following problem: N tasks must be accomplished by N persons. 1 task to be done by exactly 1 person and vice ...
20 views

### Why do we use worse-case when categorising problems?

Maybe I am wrong, but I read that when we categorise problems in their respective complexity classes, we use worse-case analysis. Why don't we use the average case? I imagine we could have a problem ...
79 views

### DSPACE(f(n)) closed under complement

I think you can create the complementary language that is an element of DSPACE($f(n)$), where $f(n) \geq \log(n)$ by adding a step to the algorithm that reverses the answer. By that the function $f(n)$...
127 views

### Proving NP completeness of maximal length path

I have this question to answer: For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the ...
33 views

18 views

### Why is $BPP^{NP}$ in the polynomial hierarchy?

Why is $BPP^{NP}$ in the polynomial hierarchy? I know that $BPP$ is contained in $NP^{NP}$, so $BPP$ is inside $PH$. Should I just simply reuse the proof of $BPP\subset NP^{NP}$, feed in each machine ...
31 views

### is this given language in class P? [duplicate]

i was wondering: is this language in class P? $NONDISJOINT_{DFA}\:=\:\left\{<A,B> |\:A\:and\:B\:are\:DFAS\:and\:L\left(A\right)\:\cap L\left(b\right)\:\ne \varnothing \right\}$ explanation: a ...
I have been trying to solve satisfiability of {$<c, w>$ | $c$ is a CNF and $w$ is a binary string which satifies the $c$}. As first looks to me, it is satisiable in linear time ($O(n)$) since ...