# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

3,720 questions
Filter by
Sorted by
Tagged with
3k views

### Graph 3-colorability is self-reducible

I am interested in self-reducibility of Graph 3-Coloralibity problem. Definition of Graph 3-Coloralibity problem. Given an undirected graph $G$ does there exists a way to color the nodes red, green, ...
5 views

### Why does such reductions work

In class we saw examples of reductions like from Independent Set(IS) to Longest common subsequence( arbitraary number of sequences) (LCS) $V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$ The ...
20 views

### How to prove NP-completeness of this variant of the set cover problem?

The problem exactly: Suppose you're helping to organize a summer sports camp, and the following problem comes up. For each of the n sports offered at this camp, the camp is supposed to have at least ...
479 views

### Are there any proofs of exponnential lower bound time complexity

I'm trying to understand what are the techniques to prove an exponential time lower bound. For some problems, we can prove that the size of the output is exponential is the size of the input, thus it ...
8 views

### What does it mean this relation: $BQP^{BQP} = BQP$

I am reading this paper by Fortnow, titled: One Complexity Theorist's View of Quantum Computing. In section 4, he states the following: Bernstein and Vazirani [BV97] show that BQP can simulate any ...
23 views

### Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?

So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
39 views

### Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to ...
53 views

### Oracle separation P and BPP

I'm reading (with much pleasure) the book Quantum Computing Since Democritus by Scott Aaronson. At some point the author claims that, while most most people believe that $\mathbf{P} = \mathbf{BPP}$ in ...
169 views

33 views

### Time Complexity of Subset Problem

The Subset Exercise taken from LeetCode: ...
18 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

### Reduce duplicate subset sum problem to distinct subset sum problem?

In duplicate subset sum problem (DuSSP), we are given a multiset $\{a_1,a_2,\ldots,a_n\}$ where some of the $a_i$ are duplicates. We can assume that $a_1\leq a_2\leq \cdots\leq a_m.$ We are also given ...
36 views

### Find minimum pair number based on selection algorithm

If we have n balls in a red box (each ball is assigned a different number from 1 to n) and n balls in a green box (again each ball is assigned a different number from 1 to n). Lets say we have a ...
17 views

### Oblivious Machines and Input Dependency

So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input ...
23 views

### If A is polynomial time reducible to B and B is in NP, then A is in NP

If $A\leq_p B$ and $B$ is in $NP$, is it true that $A$ is in $NP$? What about : "if $A\leq_p B$ and $B$ is in $coNP$, then $A$ is in $coNP$"? Thanks in advance. I think both hold. If $B$ is in $NP$...
16 views

### First attempt at convert Context-Free Grammar into Chomsky Normal Form

This is my first attempt at converting a context free grammar into chomsky normal form. I think I have the correct answer, would just appreciate any feedback if I have gone wrong somewhere. Context ...
76 views

### Is GAP NP-hard with at most two balls per bins?

The generalized assignment problem (GAP)  is given by: Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and ...
520 views

### Simple proof for NP-completeness of Edge Dominating Set

In a graph, an edge dominating set is a subset D of the edges such that any edge in the graph is either in D, or shares an endpoint with an edge in D. The Minimum Edge Dominating Set problem is to ...
220 views

### Polynomial multiplication coefficients

I was wondering about the following interesting questions: Polynomial multiplication can be done in $O(nlog(n))$ using FFT where n is the degree of the polynomial. What about finding a specific ...
20 views

### Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
21 views

### What is the complexity class of performing a perfect disassembly of binary code?

I have heard that the complexity class of performing a perfect disassembly of binary is undecidable. Is this correct? Are there any proofs of this?
45 views

### Who initiated the term “Extended Church-Turing Thesis”? or What papers that initiated this term?

I have been looking for any reference regarding the term: "Extended Church-Turing Thesis" [some people will call it, Strong Church–Turing Thesis]? Does anyone defined it or it is just people in ...
14 views

### What are the requirements for a superset of P to be closed under karp reductions?

So today in our exercise session on complexity theory we discussed that P, NP, and BPP are closed under karp reduction. We also figured that the proofs could likely be expanded to straight ...
17 views

### Post correspondence problem: Finding total number of solutions

Let $A = \{a,b\}$ be an alphabet. $P = A^* \times A^*$ An instance of the PCP is a non-empty List $D = (d_1, d_2, ..., d_n) \in P^n$ of pairs of words. To a PCP-instance $D \in P^n$ an index ...
30 views

### MaxClique is DP-hard

I want to show that MAX−CLIQUE={(G,k)|the largest clique of G is of size exactly k} is DP-complete The idea is reduce MAX-CLIQUE to C={(G1,k1,G2,k2) | G1 has a k1-clique and G2 does not ...
20 views

### Complexity of finding an alternating Hamiltonian (x,y)-path in edge bicolored complete graphs

Let $G$ be a simple complete graph with an edge-2-coloring. An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its ...
36 views

### Complexity of Hamilton path in directed complete bipartite graphs

Finding a Hamiltonian path in a directed bipartite graph is NP-complete. Problem 1 What is the complexity of the problem if we insist that the underlying graph of the digraph be complete ...
33 views

### A and B are two languages. If A is Turing reducible to B and B is Turing reducible to A, A = B?

If you could help me, I would be grateful! Thanks!
26 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 ...
22 views

### If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$

The following exercise is taken from Chapter 17 of Languages and Machines by Thomas Sudkamp: Let $Q$ be a language reducible to a language $L$ in polynomial time. Prove that $\overline{Q}$ is ...
14 views

### Is there any importance in problems whose witness for membership in a set, cannot be bounded by a polynomial?

The class NP can be defined as a polynomially bounded relation $R$. Where $x \in R$ if there exists some $y$ that has length bounded by $p(|x|)$, where $p$ is some polynomial. Why do we not study the ...
31 views

$N:=2^p$ Input: $f \in \mathbb C^N$ 1: $n=N/2$ 2: initialize vectors $f^{(1)}, f^{(2)} \in \mathbb C^n$ 3: $w_N^0=1$ 4: for $j=0,\ldots,n-1$ do 5: $\ \ \ \ \ f_j^{(1)}=f_j+f_{j+n}$ 6: $\ \ \ \ ... 0answers 9 views ### Time spent multiplying with expoDC and D&C Let$T(m,n) \leq that0$if n = 1$T(m,n/2) + M(mn/2,mn/2)$if n is even$T(m, n-1) + M(m, (n-1)m)$otherwise The time to do$a^n$where m is the size of a (the number of figures). If$M(q,s) \...
I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$ nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor. ...