Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,499
questions
1
vote
1answer
10 views
Is there a mapping reduction for every two language $A$ and $B$ to some language $C$?
One of my friend told me that there is a language $C$ for every two languages $A$ and $B$ s.t $A \leq_{m} C$ and $B \leq_{m} C$ , he simply define two languages $A’=\{0w|w \in A\}$ and $B’=\{1w|w \in ...
0
votes
0answers
8 views
Cost of solving linear equation using FFT algorithm
I have a linear equation $Cx=b$ where $C$ is $n \times n$ circulant matrix. By applying circular convolution process, vector $x$ can be solved using Fast Fourier Transform (FFT) to transform the ...
1
vote
1answer
22 views
Proof plan for P ≠ NP
Let $M$ be a Turing Machine for SAT. We want to encode certain paths of $M$ in a very short way in order to diagonalize against the paths.
For each natural number $k$, we will have a formula $\phi$ of ...
1
vote
0answers
15 views
How do we know that this Karp-Lipton theorem is derived from relativizing arguments?
Luca Trevisan wrote, " The oracle $C$ tells us that we cannot have a relativizing proof that derives the $𝑁𝑃 ⊈ 𝑃/𝑝𝑜𝑙𝑦$ conclusion from the $𝑃 ≠𝑁𝑃$ assumption, so a theorem such as Karp-...
1
vote
0answers
23 views
Prove that characteristic function $f_w$ in write protected input turing machine behave as a 2FSA
Write protected input turing machine is a single-tape TM that cannot write on the input portion of the tape. I almost prove that these TMs can only recognize regular languages but i have a problem in ...
1
vote
1answer
15 views
Is it possible to have a zero knowledge proof with a P Prover?
In the literature, when reading about zero knowledge proofs, the prover (prover/verifier) is always given an unlimited computational power or just capacity to solve NP.
Is it necessary for the prover ...
-3
votes
0answers
24 views
Set of CNFs with at least two satisfying assignments belongs to NP
Let DOUBLE-SAT = { ⟨φ⟩ | φ has at least two satisfying assignments }. Show that DOUBLE-SAT is in NP by giving a polynomial-time verifier for it and describing why the verifier runs in polynomial time.
1
vote
1answer
17 views
How to prove that the reduction relation is not symmetric
I know that the reduction relation is not symmetric. Writing formal proofs is the main core of the course I take on Theory of Computation. So I'm trying to prove that theorem. For that I need to show ...
2
votes
1answer
27 views
Has it been shown or can we show that if $SAT \in P$ then SAT can't be in any complexity class C so that $C \subsetneq P$?
I'm already guessing that the answer is no because we cannot know whether there is a class "in between" already known classes? Or can we?
I am very new to complexity theory.
Thanks for any ...
0
votes
0answers
13 views
Time complexity of calculating the eigenvalues and eigenvector of a matrix
I know the time complexity of calculating the determinant of a square matrix of order $n$ is $O(n^3)$ (by using standard matrix multiplication). What is the time complexity of calculating the ...
1
vote
1answer
29 views
How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem?
I know how to prove longest-path problem by reducing Hamiltonian Path problem.
Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-...
0
votes
1answer
26 views
Having trouble understanding blatantly non-private definition because of Little-o notation
I was pretty confident that I understand asymptotic notation until now. However, I am having a hard time understanding some basic definition that use asymptotic notation, specially little-o.
...
2
votes
2answers
37 views
Why can't one use the Cook-Levin theorem to show that TQBF is PSPACE-complete?
I have been reading Michael Sipser's Introduction to the Theory of Computation, and I have stumbled upon a paragraph in Chapter 8 (Theorem 8.9 on page 339 of the 3rd international edition) that I ...
0
votes
0answers
16 views
Bipartiteness testing in restricted cases
Bipartite testing is in Logspace and a proof is in Is deciding whether or not a graph is bipartite in $L$?.
Is there a restricted version of Bipartite testing in $NC^1$?
For example bounded degree, ...
1
vote
1answer
126 views
Proof of NP-completeness via extra information
I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$. I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \...
0
votes
1answer
43 views
The subset sum problem is not in P because the question is about lossy compressed data? Why not?
Where is there a gap or error in my reasoning?
The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1).
The compression ...
0
votes
1answer
16 views
Douglas-Peucker line simplification algorithm time complexity
I am analyzing the time complexity of the Douglas-Peucker line simplification algorithm. Reading online I've found that it has a worst-case running time of $O(n^2)$ where $n$ is the number of points ...
0
votes
1answer
30 views
DFA for language
I want to give a DFA for the language which contains the words X ∈ {0,1,2}* for which the number of 0's + number of 1's is even AND the number of 1's + the number of 2's is odd.
I tried many ...
-1
votes
0answers
15 views
Are there other translations of multiplier (satisfiability) circuitry to 4 coloring?
The translation makes factorization/primality amenable to simple depth first graph coloring with 4 colors. I am mostly just wondering if it has been done before. There are zero computational ...
-2
votes
1answer
40 views
Reduction from 3SAT to SUBSET-SUM
The reduction from 3SAT to SUBSET-SUM includes building a
table as follows:
Where base 10 representation is used for the rows in the table.
I would like to know if the reduction will still be correct ...
0
votes
1answer
13 views
SAT and Polytime Reductions
If an algorithm for $SAT$ runs in $O(n^{\log n})$ time, and if $L$ belongs to $\mathsf{NP}$, is there an algorithm for $L$ that runs in $O(n^{\log n})$ time?
0
votes
1answer
26 views
Karp's reduction strategy
One way to prove that a problem $X$ is NP-Complete is to pick two NP-Complete problems $Z$ and $W$ and show that ($\leq_p$ is polynomial reduction):
$$\begin{array}{rr}X \leq_p Z & (1)\\W \leq_p X&...
1
vote
0answers
19 views
Nisan-Wigderson generator and $\mathbf P=\mathbf{BPP}$
In this set of notes it is claimed that:
If there exists a polynomial-time pseudorandom generator $G:\{0,1\}^{O(\log n)}\to\{0,1\}^{O(n)}$ that $1/10$-fools all $n^2$-size circuits, then $\mathbf P=\...
1
vote
1answer
47 views
Is there a theorem that says when an array of numbers can be searched faster than linearly?
I'm familiar with binary search, but I'm interested in when a collection of numbers can be searched faster than checking them all one by one with any algorithm. Binary search requires sorting to work, ...
0
votes
0answers
30 views
How can I randomly sample from the set of NP Complete problems?
I'd like to create some program that can keep spitting out verification algorithms.
My verification algorithms take two inputs: problem instance, and solution (both encoded in binary), and output True ...
0
votes
1answer
29 views
Polynomially Equivalent Pairs of Minimization-Maximization Problems in Weighted Graphs
I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve Problem 9.5.14, about polynomially equivalent minimization-maximization ...
4
votes
4answers
3k views
Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?
I know this could be a strange question. But was there any algorithm ever found to compute an NP-problem, whether it be hard or complete, in polynomial time. I know this dabbles into the "does P=...
3
votes
1answer
81 views
Polynomial time optimization problems belong to which complexity class?
I know that $\mathsf{P}$ class is only defined for decision problems. Therefore, a problem like "Does there exist an $(s,t)$ path of length $k$ in the graph $G$?" is in $\mathsf{P}$. One can ...
0
votes
0answers
21 views
Understanding the Space Hierarchy Theorem and its proof
This is what I've learned from the SHT and the sketch of its proof. I would appreciate pointing out any mistake.
The intuition behind the Space Hierarchy Theorem is that
"there are Turing ...
3
votes
0answers
37 views
Minimum Vertex Cover of 2 vertex disjoint odd cycles that have edges between them
Consider the graph $G$, which is comprised of 2 vertex disjoint odd cycles ($C_1$, $C_2$) where $|C_1|$ and $|C_2| \geq 5$. $G$ is sub-cubic and connected, with edges in between the cycles. Because $G$...
2
votes
1answer
18 views
Proof that pseudorandom generators implies one-way function
I'm reading proof on Wikipedia that the existence of pseudorandom generators implies the existence of one-way functions.
My understanding is that pseudorandom generators are defined as
A function $...
1
vote
1answer
46 views
Complexity of All-SAT
All-SAT is the problem of enumerating all satisfying assignments of a boolean formula.
All-SAT is different from #SAT, where it suffices to find the number of satisfying assignments without ...
1
vote
1answer
25 views
What are the #P-hard version of Latin square and sudoku?
I know that filling partial latin square and solving sudoku are NP-hard. But what are the counting versions of these two problems?
2
votes
1answer
42 views
Is $A \leqslant_P B \iff A \in \mathsf{P}^B$? If not are there counter-examples?
The way I think of reducing problem $A$ to problem $B$ in polynomial time, i.e. $A \leqslant_P B$, is that you assume an efficient solution to $B$ which is enough to solve $A$. Now, this is ...
0
votes
0answers
18 views
How to show that if 0 < $\alpha$ < 1, RP$_\alpha$ = RP using reliability amplification [duplicate]
Let $0 \le \alpha \le 1$. The complexity classs $\mathsf{RP}_\alpha$ consists of all languages $L$ for which we can find a probabilistic polynomial time Turing machine which satisfies the following ...
2
votes
1answer
50 views
ACC0 and the majority gate
I am missing something obvious here. Does ACC0 reach a ceiling AC0[m] with m being constant?
By another description, ACC0 can use any m, which can trivially test modulus gates from [n/2,n] over all ...
0
votes
0answers
15 views
Looking for prior occurrences of $k$-CNF efficiently translated to coloring?
Has anyone else ever translated 3-cnf (4-cnf) on $N$ variables and $M$ clauses
into 4 coloring on $O(M)$ vertices? By taking two variables from a clause,
the four boolean combinations correspond to ...
1
vote
1answer
44 views
How to show that this problem is NP-hard: Find two subsets of 2 given sets such that the difference between the subset sums is $\leq v$
As input, given two finite sets of integers $X = \{x_1,...,x_m\}$, $Y = \{y_1,...,y_n\} \subseteq Z$, and a non-negative integer $v ≥ 0$. The goal is to decide if there are non-empty subsets $S ⊆ [m]$ ...
1
vote
1answer
74 views
There is an $n^k$ prover if and only if $P = NP$
I am studying computational complexity using Papadimitrious's book: "Computational Complexity".
I am trying to solve the final statement of Problem 8.4.9, but I am stuck and would like some ...
0
votes
1answer
24 views
Space complexity of a variant of st-connectivity
Consider a variant of STCON, called 2STCON, which is defined like this:
$$2STCON = \{\langle G,u,v \rangle \} \mid \text{$G$ is a graph with } \mathit{two} \text{ paths from $u$ to $v$} \} $$
This ...
1
vote
1answer
31 views
Definition of RP/poly is not clear!
In Motwani and Raghavan's textbook, p38-39, they states:
A sequence $C_1, C_2, C_3, \dots$ of circuits is a circuit family for function $f_n\colon {0,1}^n \rightarrow \{0,1\}$ if $C_n$ has $n$ inputs ...
0
votes
1answer
41 views
IS SUBSET-SUM in P if b(the sum) is given in unary and a1,…,an is in binary?
The SUBSET SUM decision problem consists of poitive integers a1,...,an; b.
We wish to know if for some subset S of the indices, $\sum_{i \in S}a_i = b$
I want to prove that if b is given in unary(...
-1
votes
0answers
29 views
Is this decision problem NP-Complete? [duplicate]
Say we have a decision problem defined as:
LOADING: Given items of weights a1,...,am, vehicles of weight capacity B, can the items be loaded onto C or fewer vehicles? (All numbers are positive ...
1
vote
2answers
65 views
Given an algorithm, is it possible to find all other equivalent algorithms for the same computable function in the same model
For any computable-function, there may be multiple different algorithms (possibly countably infinite). For example, sort has many different implementations/algorithms, that we know of or that we have ...
1
vote
0answers
36 views
How computationally hard are the battle systems of Paper Mario and Paper Mario: The Thousand Year Door?
What is the time complexity and space complexity of working out, in suitably generalised versions of the battle systems of both Paper Mario 64 and Paper Mario: The Thousand Year Door:
The minimum ...
1
vote
1answer
20 views
What are the differences between Oracle Turing Machine and PAC?
I am having difficulty understanding the difference between PAC and Oracle Machines. I cannot compare these two in terms of uncertainty and physical effort.
The degree of uncertainty we can tolerate ...
4
votes
0answers
41 views
Problems that are easy on boolean formulas but become NP-hard on circuits?
Many problems that take a boolean circuit as input are NP hard to compute. Do we have examples of such problems that become polynomial time computable when only boolean formulas are allowed as input?
...
2
votes
1answer
35 views
How is Hypergraph Isomorphism (HI) reduced to Graph Isomorphism (GI) in polynomial time?
This question states that the problem of Hyper-graph Isomorphism is equivalent to Graph isomorphism. I have not been able to find a description of the reduction so I am wondering how that might work ...
-1
votes
1answer
47 views
Solve the following recurrence
I'm trying to solve this the recurrence :
$$
T(n)=\begin{cases}
1, & \text{ if } n = 1 \\
T(n-1) +n(n-1), & \text{ if } n \geq 2
\end{cases}
$$
0
votes
1answer
96 views
Could the empty language be NP-Complete?
I think the empty language is NP but I'm not sure if it is NP-Complete
