Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,955
questions
0
votes
0
answers
24
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,039
0
votes
0
answers
26
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 ...
- 304
0
votes
0
answers
103
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 ...
6
votes
0
answers
118
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
10
votes
12
answers
4k
views
Theoretical Computer Science vs other Sciences?
So I‘m in my third 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, ...
- 117
-1
votes
0
answers
40
views
Do modular exponentiation and extended GCD have any $Logspace$ relation between them?
Modular exponentiation and Extended $GCD$ are notorious open problems in parallel computational complexity domain.
Is there any $Logspace$ or lower relation or reduction between them at least under ...
- 12.6k
4
votes
2
answers
157
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 ...
- 397
3
votes
0
answers
90
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
99
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 ...
- 151
0
votes
1
answer
103
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. ...
2
votes
0
answers
90
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 ...
- 153
3
votes
1
answer
75
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
4
votes
0
answers
89
views
What are the implications if you could derandomize constant depth polynomial identity testing over $\mathbb{Z}$?
As far as it goes, I read that derandomizing depth-4-$PIT$ over finite fields is already a great achievement since it would mean a subexponential deterministic time algorithm for the general case and ...
- 153
5
votes
2
answers
158
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
95
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
143
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
213
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 ...
- 153
7
votes
0
answers
96
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}$, ...
- 71
0
votes
0
answers
226
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,039
4
votes
0
answers
102
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,859
2
votes
0
answers
52
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
401
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 ...
- 862
3
votes
2
answers
93
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 ...
- 889
2
votes
0
answers
122
views
Is modular square roots in NC?
Assume factorization of modulus is known. Is modular square roots then in $NC$?
How about the case of prime modulus?
- 12.6k
0
votes
1
answer
63
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,697
0
votes
0
answers
54
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
0
votes
0
answers
79
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
90
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 ...
- 1,880
2
votes
1
answer
117
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 ...
- 317
7
votes
0
answers
81
views
Does Bellantoni-Cook safe recursion (or any other implicit characterization of P) admit Kleene's second recursion theorem?
Abstractly, by a programming language that operates on binary strings I mean a set $P$ of programs along with a semantics relation $[p](x) = y$, ``the program $p$ on string $x$ halts with output $y$.&...
- 483
0
votes
0
answers
125
views
Savitch's theorem for time complexity
Is it known that an analog of Savitch's theorem for time complexity is impossible, or is this an open question?
More formally, is $\exists d\ \forall c : \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(n^...
7
votes
1
answer
237
views
Is $PSPACE$ believed to be different than $PP$?
From Googling, I couldn't find any discussion about whether $PP=PSPACE$ is more or less likely than $PP\subsetneq PSPACE$.
Is it currently believed that $PP\neq PSPACE$?
What would be the ...
- 215
6
votes
1
answer
285
views
Concrete family of propositional formulas
Let $k,n \in \mathbb{N}$, where $k$ can be thought of as being fixed constant. For each $1 \leq \ell \leq k$ and $1 \leq i \leq n$ we have a proposition symbol $p_{(\ell,i)}$ (so in total we have $nk$-...
- 869
0
votes
0
answers
91
views
Non-uniformity assumptions in circuit complexity
I recently came accross the following standard inclusion of complexity classes:
$$\textbf{NC}^0 \subseteq \textbf{AC}^0 \subseteq \textbf{NC}^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \...
- 557
7
votes
1
answer
238
views
How do separations in of query complexities imply complexity class separations relative to oracles?
Simon's problem is the following: Given oracle access to a Boolean function $f: \{0,1\}^n\rightarrow \{0,1\}^n$, and promised that precisely one of the following two cases is true, decide which of ...
- 250
0
votes
0
answers
52
views
Non-uniform consequences of uniform derandomization
Adleman showed that $\mathsf{BPP/poly} \subseteq \mathsf{P/poly}$.
Does $\mathsf{P} = \mathsf{BPP}$ have any implications for
$\mathsf{BPP}/a(n) \subseteq \mathsf{P}/a(n)$
$\mathsf{BPTIME}(t(n))/a(n) ...
1
vote
0
answers
65
views
One way analogues of Logspace
When we say a function is one-way we typically mean a function is encodable in $P$ but its decryption is not in $P$ but in $UP$.
Likewise we say a function is logspace one-way if the function is ...
- 12.6k
2
votes
0
answers
97
views
Problems in $P^{PP}$
I just discovered that a problem that I was studying could belong to $P^{PP}$, I would like to prove that this problem is $P^{PP}$-complete (if that is even a thing). The issue is that I'm unable to ...
- 21
11
votes
1
answer
1k
views
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
- 8,224
2
votes
0
answers
109
views
Computing real numbers with Turing Machines
Consider the following decision problem:
Given a two integers $n$ and $k$, decide whether $k=\lfloor n\pi\rfloor$
Question: Is this problem known to be in $P$?
Although this may look like a stupid ...
- 475
0
votes
0
answers
67
views
On the Reductions of Functional complexity Classes
In Chapter 10 of Computational Complexity by Christos Papadimitriou, it is noted that reduction between problems of functional complexity classes are defined as follows:
Function problem A reduces to ...
- 21
5
votes
0
answers
160
views
Complexity of a problem related to Friedman's TREE(k) function?
Background
Given two rooted, vertex-colored trees $T_1, T_2$, $T_1$ is color-preserving inf-embeddle in $T_2$, which we'll denote $T_1 \leq T_2$, if there is an injective $f \colon V(T_1) \to V(T_2)$ ...
- 36.3k
2
votes
0
answers
77
views
Random Self-Reducibility of the Discrete Logarithm
Section 10.1.2 of Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach defines random self-reducibility and proves hardness of the discrete logarithm by reducing a worst case ...
- 21
5
votes
2
answers
235
views
Complexity of convertibility in simply typed λ-calculus with sums
For the simply typed λ-calculus with only the function type →, the complexity of deciding βη-equivalence is well-understood: it's TOWER-complete (as mentioned here). I expect the same should be true ...
1
vote
0
answers
98
views
On the borderline between natural and artificial problems
While there is no formal definition of what constitutes a natural algorithmic problem,
in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
- 10.8k
0
votes
1
answer
62
views
PAC learning over continuous functions
I'm wondering if it's possible to use PAC learning to learn a continuous function. For example, if we wanted to learn a probability distribution or a CDF, is it valid to train on some set of m ...
- 1
0
votes
0
answers
63
views
Universality problem over unary alphabet is NP-complete
The universality problem over a unary alphabet: Decide if a unary NFA rejects a string.
I believe that this is NP complete, but I am unsure of how to prove it. One possible idea I have is to split it ...
0
votes
0
answers
70
views
How does laziness help functional data structure?
Functional data structures, or immutable data structures, are often achieved by copying old data to new data upon operation. Naively, it looks much less efficient than their imperical counterpart. ...
- 127
2
votes
0
answers
38
views
Statements equivalent to strongly polynomial time linear programming
Say a problem is SPT iff it admits an SPT algorithm. What statements of interest are known to be equivalent to "LP is SPT"? Examples:
"linear feasibility solving is SPT" (due to ...
- 642
3
votes
3
answers
258
views
Intersection non-emptiness problem over regular expressions and NFA
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 ...
- 889