Questions tagged [complexity-classes]
Questions about relationships between complexity classes.
359
questions
1
vote
0answers
13 views
What about problems that are fixed parameter tractable with an algorithm that does not inspects the parameter
A parameterized problem is a subset $L \subseteq \Sigma^* \times \mathbb N$, where $\Sigma$ is a finite alphabet. A parameterized problem is fixed parameter tractable, if it could be decided in time $...
0
votes
1answer
30 views
$\text{DSPACE}(O(1))=\text{REG}$ Proof?
I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
2
votes
2answers
38 views
Logarithmic space verifier with unbounded witness
this is a HW question, but its considered a bonus question so I'd appreciate a direction.
Definitions:
The actual question:
**Images taken from HW in TAU Complexity course by Amnon Ta-Shma.
My ...
0
votes
2answers
62 views
How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $
I am trying to answer this question:
$3x^3 +2x + 1$ is $ \omega(x \cdot \log x)$
My question is how to solve this question.
Here is what I have tried so far:
I applied the definition $3x^3 + 2x + 1 ...
2
votes
1answer
33 views
Complexity classes closed under finite union and intersection, why not infinite union and intersection?
All "nice" Complexity classes are closed under finite union and intersection. (By "nice" I mean ones with complete problems or leaf languages, e.g. P, NP, PSPACE, etc.)
But such classes are not ...
8
votes
1answer
1k views
Can any problem in P be converted to any other problem in P in polynomial time?
Is it possible to convert any problem in P to any other problem in P in polynomial time?
1
vote
1answer
39 views
What complexity class is this set of grammars?
Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, ...
3
votes
1answer
28 views
How to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages
I think this is a basic topic in complexity, but I would like to ask how to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages. From the definition of my textbook, $$co-\mathcal{L}...
1
vote
2answers
23 views
Proof that uniform circuit families can efficiently simulate a Turing Machine
Can someone explain (or provide a reference for) how to show that uniform circuit families can efficiently simulate Turing machines? I have only seen them discussed in terms of specific complexity ...
1
vote
3answers
120 views
Is this a Fixed Parameter Tractable algorithm?
Suppose my algorithm runs in time $O(nL^2)$, where $n$ is the size of the input, and $L$ some other parameter, which can get arbitrarily large w.r.t. $n$. My algorithm does not run in polynomial time, ...
1
vote
1answer
21 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
42 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
40 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
39 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, ...
0
votes
0answers
18 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 ...
1
vote
0answers
83 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-...
3
votes
1answer
93 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
28 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 ...
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), ...
0
votes
1answer
32 views
how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$
how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then
${NP = P ? }$
2
votes
1answer
88 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 ...
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?
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$ ...
3
votes
1answer
102 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
33 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
42 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
38 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
38 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 ...
0
votes
1answer
72 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
vote
1answer
82 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)$?
2
votes
1answer
71 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
89 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....
1
vote
1answer
110 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 ...
0
votes
2answers
276 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 ...
5
votes
0answers
109 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 ...
4
votes
1answer
488 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 ...
1
vote
1answer
72 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
2answers
211 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
1answer
98 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 ...
1
vote
0answers
24 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 ...
0
votes
1answer
86 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 ...
1
vote
1answer
41 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
20 views
$P$ with $SAT[k]$ and $NP[k]$ oracles?
We know $coNP$ is in $P^{NP}$ and so does $coNP$ in $P^{NP[1]}$ and $P^{SAT[1]}$ hold?
Is there a difference between $P^{SAT[k]}$ and $P^{NP[k]}$ at any $k\geq0$?
0
votes
0answers
46 views
Intersection of decision problems?
Say we have two problems $\Pi_1\in NP$ and $\Pi_2\in coNP$. Where does $\Pi_1\cap\Pi_2$ live?
0
votes
1answer
44 views
prove that there is a complete language in $L \cup \{A_{TM}\}$
$A_{TM} = \{\langle M,w\rangle\mid w\in L(M)\}$
$L$ = complexity class containing decision problems that can be solved by a deterministic Turing machine using logarithmic space
Given the language $L ...
2
votes
0answers
54 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 ...
1
vote
1answer
35 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 ...
1
vote
2answers
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 ...
