Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
8
votes
2answers
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, ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
4
votes
2answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
4
votes
0answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
169 views

Rigorous definition of efficient algorithm that $\epsilon$-refutes random 3CNF formulas

I recently asked a similar question, however, I'd like to address it in a more mathematically precise setting. In that paper, on page 5, it talks about a rigorous definition of what it means to $\...
0
votes
1answer
78 views

Is this statement of P = NP in Agda correct?

Looking for a self-contained statement of P = NP in type theory, I stumbled upon this short Agda formalization (a cleaned up version is reproduced below). The statement here does seem to express the ...
2
votes
1answer
28 views

Interactive proof system for graph nonisomorphism

$\mathit{GNI} \in \mathrm{PCP}(\mathit{poly}(n),1)$ GNI is the language of nonisomorphic graphs. Given two grapsh $G_0$ and $G_1$ with $n$ vertices, a verifier expects $\pi$ to contain, for each ...
1
vote
1answer
40 views

Categorising problems into complexity classes

Am I correct in saying that there are two ways to categorise a problem in complexity theory: Find an algorithm that solves it. If the algorithm runs in polynomial time, then we can put it into P-...
15
votes
3answers
3k views

Why not to take the unary representation of numbers in numeric algorithms?

A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits). For example testing whether ...
1
vote
1answer
22 views

The space complexity of a function that allocates space based on the input value and not size

What is the space complexity of the following hyphotetical function: void function(int n) { int[] array = new int[n]; // allocate array of size n return; } ...
1
vote
1answer
24 views

Reductions from non decision problems

I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min ...
0
votes
2answers
16 views

Decide whether an $n$-bit positive integer is composite

Question: Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP? I know that for every composite number, a factor of the number is a ...
4
votes
3answers
3k views

Show that P is closed against the Kleene star

I have that question that looks kinda easy at first but it is quite hard. Let $L\in P$. Prove that $L^*\in P$ my approach: I tried to generate a Turing machine but I got stuck with the thing of ...
6
votes
1answer
61 views

Is 3-colouring NP-hard for 5-colourable graphs?

Recently it was shown that it is NP-hard to find a 5-colouring of a 3-colourable graph. More generally, it is NP-hard to distinguish $k$-colourable graphs from those that are not $(2k-1)$-colourable, ...
2
votes
1answer
49 views

Partition into pairs with minimum absolute difference, NP-hard?

I have a set $S$ of an even number of positive elements $2m$ and $m$ values $t_1,t_2,\ldots,t_m$ where each $t_i\leq1$ for all $i$. The question is: can you select $m$ disjoint pairs $(a_i,b_i)$ from ...
2
votes
1answer
81 views

Can we solve this problem more efficiently than trying all possible combinations

Here is the context of the problem I am struggling with. I have a set of strings, for example: ...
1
vote
2answers
41 views

Multivariate polynomials

Given a Diophantine equation $p(x_1,x_2,...,x_n)$, Can I find a reduction from $\text{dioph}(\mathbb{N}) \leq \text{dioph}(\mathbb{N}_e)$? $\mathbb{N}_e$ is the set of even numbers. So I have to ...
0
votes
1answer
65 views

pseudo-polynomial reduction from 3-Partition to Partition

A problem $\Pi'$ is pseudo-polynomially reducible to the problem $\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially ...
24
votes
2answers
6k views

“NP-complete” optimization problems

I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. ...
-2
votes
2answers
70 views

Show that: $0.01n \log n - 2000n+6 = O(n \log n)$

Show that $0.01n \log n - 2000n+6 = O(n \log n)$. Starting from the definition: $O(g(n))=\{f:\mathbb{N}^* \to \mathbb{R}^*_{+} | \exists c \in \mathbb{R}^*_{+}, n_0\in\mathbb{N}^* s. t. f(n) \leq cg(...
1
vote
0answers
33 views

Time Complexity of Subset Problem

The Subset Exercise taken from LeetCode: ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
-1
votes
0answers
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$...
0
votes
0answers
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 ...
5
votes
1answer
76 views

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

The generalized assignment problem (GAP) [1] 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 ...
8
votes
3answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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?
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
31 views

Number of multiplications and additions in the given code

$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: $\ \ \ \ ...
0
votes
0answers
9 views

Time spent multiplying with expoDC and D&C

Let $T(m,n) \leq that$ $0$ 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) \...
4
votes
2answers
92 views

Are SAT problems with at most two false clauses NP-complete?

Is the problem of deciding whether a SAT instance, where at most two clauses are false (that is, any given variable assignment will either lead to all clauses being true, all but one, or all but two), ...
1
vote
1answer
91 views

Space complexity of breadth-first search

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. ...