Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

4,750 questions
Filter by
Sorted by
Tagged with
38 views

Transitions of Turing machine in Cook Levin theorem proof

I am looking at the proof of the Cook-Levin theorem in Computers and Intractability: A Guide to the Theory of NP-Completeness. In particular, I find one thing ...
28 views

What class is the language $(C,(v_i)_{i=1}^m,x)$ complete to s.t. $C(x)$ is a boolean circuit with $m$ gates with values $\{v_i\}_{i=1}^m$

Given the following language:  L=\left\{\,(\,C,\,\{v_i\}_{i=1}^m, \,x\,) \enspace :\enspace \substack{C(x) \text{ is a boolean circuit with } m \text{ gates} \\i\text{'th gate value is } v_i \text{...
32 views

Check if the given satisfying assignment of CNF formula is lexicographically the first

If there is a CNF Boolean formula in $n$ variables then the potential satisfying assignments are the binary strings of length $n$. Given a CNF Boolean formula and a satisfying assignment how ...
39 views

35 views

Decidable languages unconditionally not in P/poly

What are some nice/natural examples of languages not contained in $P/\mathit{poly}$, preferably decidable ones? I'm interested in unconditional results rather than examples such as the Karp–Lipton ...
50 views

82 views

If P!=NP, does there exist infinite hierarchy of languages between P & NP?

This looks to me as some tweaking or generalization of Ladner's result on NP-I languages, can some help me in the right direction? or redirect me to some sources where this generalization is ...
67 views

Does there exist a language O such that $NL^O= Dtime(n^{logn})^O$? How to proceed with the proof in either case?

I do have some intuition(although I would like to be corrected) regarding why $NL!=Dtime(n^{log n})$ as for some $L \in Dtime(n^{log n})$ it might be required for the TM deciding it to read inputs of ...
61 views

Square of a directed graph $G=\left< V, E\right>$

I have this question from CLRS book please. Question: The square of a directed graph $G=\left< V, E\right>$ is the graph $G=\left< V, E^2\right>$ such that $(u,w) \in E^2$ iff for some ...
185 views

What is the regular expression for the language, {w | w does not contain the substring 11}

{w | w does not contain the substring 11} What I am thinking: $(0^* 1 0^* )^*$ Is anything wrong with my expression? Thanks in advance for your help!
87 views

One-tape Turing machine for doubling words (strings)

I am going to design a Turing machine for doubling any words. My algorithm is such that for word X as input, the output will be in the form X@X which @ is a character. How can design an one-tape ...
26 views

Finding maximum clique given, for each edge, union of all cliques containing it

For every edge $e\in E$ of a graph $G=(V,E)$ we know the union $U_{e}$ of the edges of all cliques that contain $e$. Can we determine, in polynomial time, for a given edge $e_{0}\in E$, the size of ...
17 views

Where does this Oracle Problem belong in the Polynomial Hierarchy?

Given a problem $E_0$ such that: Any valid solution $S_0$ if there is any is of polynomial length. Assuming we are able to guess the solution $S_0$, for it to be valid: i. There are a fixed set of ...
A successful search takes $\Theta(1 + \alpha)$ time on average when resolving collisions by chaining
I would to discuss a proof found in CLRS book please. Theorem: In a hash table in which collisions are resolved by chaining, a successful search takes time $\Theta(1 + \alpha)$, on the average, under ...