Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
3,022
questions
4
votes
1
answer
69
views
Does there exist constant overhead reduction between common cryptographic primitives?
I have proved that there exist such reduction between error-correcting codes and exposure resilient functions, which is because that the transpose of a generator matrix for a ERC mapping $\mathbb{F}_2^...
1
vote
0
answers
71
views
Consequences of a $Parity$ $P$-problem being reducible to a sparse language?
$Parity$ $P$ is the class where an $NP$-machine answers $YES$ if and only if the number of accepting paths of that turing machine is odd.
With regards to the $P$ vs $NP$ question, there is a theorem ...
user69160
7
votes
2
answers
1k
views
Problems in NP with non-trivial certificate
For all NP-complete problems I can think about, the problem statement says very clearly how to test a certificate. I'm looking for interesting problems with NP which have non-trivial certificates. I ...
- 464
10
votes
1
answer
300
views
Does $NC=P$ imply the collapse of Polynomial Hierarchy?
If $NC=P$ (with a constructive polynomial time algorithm that converts any $P$ time circuit to a $NC$ circuit), what impact would it have on the rest of the Polynomial Hierarchy?
Couldn't find much in ...
- 468
0
votes
1
answer
123
views
Complexity of "opposite" version of a variant of #Positive-2-SAT
In this post ,I introduced a new variant of #Positive-2-SAT .
This version of problem puts restrictions on the inputs of the
#Positive-2-SAT such that we can only choose at max only 2 clauses from ...
- 13
3
votes
0
answers
147
views
The $O(n^{1/r})$ upper bound of polynomial degree of OR over composite moduli
$\newcommand{\OR}{{\sf OR}}
\newcommand{\MOD}{{\sf MOD}}
$In the paper Representing Boolean functions as polynomials modulo composite numbers, Barrington, Beigel and Rudich showed that $\delta_m(\OR_n)...
- 131
3
votes
0
answers
101
views
How do we show directly coNP is in MIP?
I know one can show that by $\mathsf{coNP}\subseteq\mathsf{NEXP}=\mathsf{MIP}$. But here I would like to start with a $\mathsf{coNP}$-complete problem and show there is a two-prover one-round ...
- 139
8
votes
1
answer
296
views
What is the general consensus on the NL vs P question?
As it stands, we know that NL is a subset of P, but we do not know if it is a proper subset or not. With that said, what is the general consensus? Do the majority think that NL = P or not? What would ...
1
vote
1
answer
101
views
Explanation of Complexity class $S_2^P$?
I am trying to understand the complexity class $S_2^P$ defined as (https://en.wikipedia.org/wiki/S2P_(complexity)). A language L is in $S_2^P$ if there exists a polynomial-time predicate $P$ such that:...
- 468
10
votes
1
answer
805
views
Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?
Recently, I came across the problem of figuring out whether a given binary function $f(x)$ is constant (0 for all values of $x$ or 1 for all values of $x$) or balanced (0 for half of values and 1 for ...
- 119
2
votes
1
answer
90
views
Fine-grained average-case derandomization
Many believe derandomization with polynomial overhead, $\mathsf{P} = \mathsf{BPP}$,
because it follows from $2^{\Omega(n)}$ circuit lower bounds for $\mathsf{E}$ (IW97).
Do we have any evidence for or ...
- 223
3
votes
1
answer
198
views
Priority queue implementation with both find-min and delete-min $o(\log n)$
Question: There are several priority queue implementations listed on Wikipedia, along with amortized complexities of each of their basic operations: Does anyone know of an implementation in which the ...
1
vote
0
answers
48
views
Oracle for the permanent-of-gaussians problem
In this paper, Aaronson and Arkhipov formulate the $GPE_\times$ problem as follows: given an $n \times n$ matrix $X$ of i.i.d. Gaussian random numbers, find the permanent of $X$ up to multiplicative ...
- 111
7
votes
0
answers
171
views
Baker–Gill–Solovay Theorem: why $2^n/10$ steps?
Context
I'm teaching an introductory complexity theory course right now and although I work in adjacent areas, I'm not an expert on complexity theory myself, so I'm still in the process of working ...
- 273
3
votes
1
answer
224
views
Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable
It is known that the problem of integer linear programming is NP-hard, but its fractional relaxation can be solved in polynomial time. The concept of fractional relaxation can be applied to any ...
- 2,078
1
vote
0
answers
85
views
Perm and Det mod $2^k$ - II
Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log ...
- 12.8k
2
votes
1
answer
116
views
Perm and Det mod $2^k$ - I
Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log ...
- 12.8k
2
votes
0
answers
77
views
Variants of complexity classes that allow "adversarial inputs"?
Wikipedia defines BPP as follows:
Alternatively, BPP can be defined using only deterministic Turing machines. A language L is in BPP if and only if there exists a polynomial p and deterministic ...
- 271
4
votes
0
answers
250
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
- 20.8k
0
votes
0
answers
35
views
Is SZK dependent on the verifier’s model of computation?
What if instead of a probabilistic TM, the verifier in the definition of SZK was a quantum TM?
How would this affect its relation to other classes? Would Statistical Difference still be a complete ...
0
votes
1
answer
74
views
Exchange cards with sum requirement
Given are positive integers $a_1,\dots,a_{2k},b_1,\dots,b_{2k},S$ such that $\sum_{i=1}^ka_i = \sum_{i=k+1}^{2k}a_i = S$ and $\sum_{i=1}^kb_i = \sum_{i=k+1}^{2k}b_i = S$. There are $2k$ cards, card $i$...
- 123
2
votes
0
answers
65
views
Open Quantum Analogs to Classical Problems
I am looking for interesting examples of complexity-theoretic and cryptographic problems where we have a significant amount of knowledge about the classical version of the problem, but we have no ...
- 121
2
votes
1
answer
211
views
Examples for Real-time vs Linear time
A real-time Turing machine (with multiple tapes) runs in linear time. It is known [1] that there are languages recognizable in linear time by a multitape Turing machine but not recognizable in real-...
- 303
0
votes
0
answers
48
views
Complexity of XOR-Knapsack
Edit: Actually I should have been more careful. Maybe the optimal way to solve this is to approach it as a series of $k'-$XOR sum problems (Generalized birthday due to Wagner) for increasing $k'.$ And ...
- 2,070
0
votes
0
answers
49
views
Reduction of Monotone-1-in-3-SAT to Cubic-Monotone-1-in-3-SAT
3-SAT is an NP-Complete problem. Now given a 3-SAT instance it can be transformed to a Monotone-1-in-3 SAT instance thus even Monotone-1-in-3-SAT is NP-Complete (am aware of this reduction).
But, as I ...
- 468
0
votes
1
answer
322
views
Is it known that P $\neq$ NP implies BQP $\neq$ NP?
Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But ...
- 101
6
votes
0
answers
154
views
Consequences of $P^{NP[o(n)]} = P^{NP}$
I am wondering what the consequences of $\text{P}^{\text{NP}[o(n)]} = \text{P}^{\text{NP}}$ are. Does this imply the collapse of the polynomial hierarchy or contradict something like $\text{ETH}$?
I ...
- 61
11
votes
12
answers
5k
views
Theoretical Computer Science vs other Sciences?
So I‘m in my fifth semester studying Computer Science at a German university, so I‘ve only scratched the surface of Theoretical Computer Science, namely Logic, Formal Languages, Automata Theory, ...
- 127
4
votes
2
answers
193
views
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
My question is the directed version of this one. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback ...
- 421
3
votes
0
answers
99
views
$\mathsf{coNP}^{\mathsf{\#P}}$ and $\mathsf{coNP}^{\mathsf{\#P}^\mathsf{\#P}}$
I was reading a paper that demonstrates that deciding whether a loop-free program is $\varepsilon$-differentially private is $\mathsf{coNP}^{\mathsf{\#P}}$-complete. What are some other problems that ...
- 131
5
votes
0
answers
113
views
How is inapproximability by polynomial size circuits sufficient for the Nisan-Wigderson generator?
I couldn't understand how exactly Yao's XOR lemma was used to prove the following claim made in the proof of Theorem 2 of the original paper describing the Nisan-Wigderson generator, so I decided to ...
- 201
0
votes
1
answer
139
views
Sources that prove solving 2-SAT with DP takes linear time
Would anyone have any sources that describe/an explanation of how solving 2-SAT using dynamic programming takes a linear amount of time? Can't seem to find a text that proves it in detail/formality. ...
3
votes
0
answers
99
views
Complexity of checking if a given prime number can be computed using at most $s$ addition/multiplication operations?
Given are a prime number $p$ and a parameter $s\in\mathbb{N}$.
What is the computational complexity of the problem of determining whether $p$ is computable by a series of at most $s$ steps, each being ...
user67795
3
votes
1
answer
90
views
END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node
The END OF THE LINE problem is stated as
Given two circuits, P and N, a node, v, is balanced if $P(N(v)) = N(P(v)) = v$ or $P(N(v)) \neq N(P(v)) \neq v$. Given that $0^n$ is not balanced, find ...
- 135
5
votes
2
answers
178
views
Lower bound for sorting without using a decision tree model
Can we prove the lower bound for the sorting problem just by Turing machine model?
It seems that available proof of sorting is based on the assumption that the algorithm only uses comparison so we can ...
- 51
4
votes
1
answer
109
views
NC0 randomnes vs. non-uniformity
In
Ajtai and Ben-Or. A theorem on probabilistic constant depth
Computations. STOC '84, 1984
Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.
Is there a similar relation known for ...
- 41
0
votes
1
answer
152
views
What is the simplest one-way function (in terms of boolean circuit complexity)?
What is the simplest known one-way function?
By simplest, I mean, when implemented as boolean logic, the number of AND/OR/NOT gates needed is minimal (smallest circuit complexity).
(I'm trying to find ...
8
votes
1
answer
230
views
Is it $NP$-hard to check whether a given algebraic circuit computes permanent?
Given are a natural number $n\in\mathbb{N}$ and a polynomial $P$ in the form of an arithmetic circuit $C$ over $\mathbb{Z}$ (a circuit which only uses $+$ and $\times$ gates and integer constants as ...
user67795
7
votes
0
answers
113
views
Complexity of the unique homomorphism problem up to automorphisms
I am interested in the following problem: given two relational structures $\mathbf{A},\mathbf{B}$,
is there a unique homomorphism from $\mathbf{A}$ to $\mathbf{B}$ up to automorphisms of $\mathbf{B}$, ...
- 143
1
vote
0
answers
335
views
Claimed proof of PSPACE ⊆ BQP on arXiv
A new paper appeared on arxiv: PSPACE ⊆ BQP by Shibdas Roy: https://arxiv.org/abs/2301.10557
From the abstract:
The complexity class PSPACE includes all computational problems that can be solved by a ...
- 2,070
4
votes
0
answers
106
views
$\mathsf{NL}$ vs. $\mathsf{AC}^1$
It is known that $\mathsf{NL} \subseteq \mathsf{AC}^1$ (because $\mathsf{NL}$-complete problem PATH belongs to $\mathsf{AC}^1$).
Are there problems in $\mathsf{AC}^1$ that are unknown to be in $\...
- 1,973
2
votes
0
answers
59
views
hardness of partition of permutation into a minimum number of monotone subsequences
Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization ...
- 71
2
votes
1
answer
421
views
Are regular expressions inherently more difficult to construct than DFAs for humans?
When I am asked to construct a regular expression and DFA that would accept a language $L$, I usually find it much easier to construct the DFA (almost coming mechanically for me) than it is to ...
- 1,088
3
votes
2
answers
118
views
Encoding of finite automata in Intersection Non-Emptiness problem
The intersection non-emptiness problem is defined as follows:
Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a ...
- 921
3
votes
1
answer
248
views
Is modular square roots modulo primes in $NC$?
Assume modulus is prime. Is modular square roots then in $NC$?
If not then, are there special primes or prime powers or numbers related to these (such as $2^k\pm i$ where $i\in\{-1,0,+1\}$) where it ...
- 12.8k
0
votes
1
answer
67
views
Require Hamming weight in CNF
I have a SAT problem in conjunctive normal form that I’d like to solve, but I need to add one more condition: for the existing variables $x_1,\ldots,x_n$ the Hamming weight is $k$. (It would be ok to ...
- 1,737
0
votes
0
answers
56
views
Restrictions on set of infinitely many n's for which an algorithm breaks distributional hardness
Say we want to capture the notion that an efficiently samplable distribution $D(1^n)$ is hard with respect to some boolean function $f$ for a decision problem or some efficient relation $R$ for a ...
- 117
1
vote
0
answers
89
views
Is complexity class containment preserved relative to any oracle?
That is, suppose $A\subseteq B$ for two complexity classes $A$ and $B$. Is it the case that for any oracle $C$, and any definitions $A^*$ and $B^*$ of $A$ and $B$, we have ${A^*}^C\subseteq {B^*}^C$? (...
0
votes
0
answers
95
views
How to prove that a given class of convex programs cannot be solved by linear programming?
Given the following program, where $f, g$ are convex functions:
$$
\text{minimize}~~ f(x)
\\
\text{subject to}~~ g(x)\leq 0
$$
the problem can be solved by convex programming algorithms, but it would ...
- 2,078
2
votes
1
answer
136
views
Counting argument for LTF circuits
In Boolean circuit complexity, Shanon's counting argument shows that a random Boolean function on $n$-input bits requires a circuit of size $\Omega(2^n/n)$ to be computed by a circuit made of AND, OR ...
- 327