Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,944
questions
0
votes
1
answer
112
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 ...
6
votes
1
answer
148
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 ...
5
votes
0
answers
61
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}$, ...
- 51
0
votes
0
answers
21
views
Complexity of feasibility of a system of linear and restricted non-linear inequalities
I have a system of constraints on $\mathbb{N}^n$ of the form $Ax \le b \land x_1 \le x_2x_3 \land x_1 \le x_4x_5$ where $A,b$ are a matrix and a vector with integer coefficients.
If there was a single ...
- 889
0
votes
0
answers
200
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
95
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,787
-3
votes
0
answers
76
views
Relation between $NC^i$ and $L^i$
Is it true $NC^i\subseteq L^i\subseteq NC^{i+1}$ at every $i>0$?
- 12.6k
2
votes
0
answers
49
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
391
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 ...
- 812
3
votes
2
answers
87
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
121
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
60
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
53
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
85
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
112
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
77
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$.&...
- 463
0
votes
0
answers
119
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
231
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
280
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$-...
- 870
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 \...
- 547
7
votes
1
answer
229
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
49
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
64
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
95
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 ...
- 7,942
2
votes
0
answers
108
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
66
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
156
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.2k
2
votes
0
answers
74
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
233
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
97
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
60
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
61
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
68
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
37
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
222
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
2
votes
1
answer
55
views
Complexity of reachability in fractal mazes with traps
Is reachability in fractal mazes with traps EXPTIME complete?
A fractal maze includes one or more copies of itself. For example, see the question Decidability of Fractal Maze or Puzzling ...
- 2,402
0
votes
0
answers
53
views
Uniformly redistributing items across bins. What problem is this?
I'm trying to find reading material on a particular problem I'm interested in, but I don't know the terms to search.
Problem assumptions/definitions:
We have finite number of items I with weights [0, ...
- 101
4
votes
0
answers
72
views
MIP with bounded communication between provers
Are there any known results on the complexity class that is MIP except with independence of provers loosened to allow "limited classical communication" between provers: where total message ...
- 141
2
votes
0
answers
106
views
Question about #P-completeness and NP-completeness
In the book Nature of Computation by Moore & Mertens there is an exercise saying "show that if a counting problem #A is #P-complete with respect to parsimonious reductions, that is if every ...
- 21
1
vote
0
answers
18
views
Coloring the $k$-deletion graph “constructively”
For $n,k\ge 1$, we define the graph $D_{n,k}$ to have vertex set $\{0,1\}^n$, with distinct $x,y$ being adjacent if $LCS(x,y)\ge n-k$.
My question is: fixing $k>1$, does there exist some $C=C_k$ ...
- 519
0
votes
0
answers
92
views
3SAT instances where no assignment fails to satisfy more than one clause: do they eixst, and what complexity class do they belong in?
Title says it all. I am curious of the 3SAT problem but limited to instances where only one clause is left unsatisfied by any literal assignment.
Do such problems exist, and if they do, what is it ...
- 101
4
votes
0
answers
302
views
Complexity of Computing Shannon Entropy
It is my understanding that the necessity of numerical precision can be an obstacle when trying to show a decision problem's membership in a particular complexity class. For example, I believe it is ...
2
votes
0
answers
67
views
Parallel complexity of fixed dimension fixed constraints integer programming
Papadimitriou in https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf shows ILP is fixed parameter tractable in number of constraints and Lenstra in https://people.csail.mit....
- 12.6k
-1
votes
1
answer
92
views
Does the set $P$ contain only decision problems or also optimization problems? [closed]
Looking at many posts on Stack Overflow, it seems the set $P$ has only decision problems. See for instance the accepted answer here.
But, this seems to be in contradiction to the book Introduction to ...
- 109
0
votes
0
answers
73
views
Boolean vs algebraic circuits difference
Valiant, Skyum, Berkowitz and Rackoff in https://epubs.siam.org/doi/10.1137/0212043 showed that $VP=VNC^2$, namely, that arithmetic circuits can be parallelized.
What is the central reason such a ...
- 12.6k
6
votes
1
answer
293
views
Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82
I was reading the paper "Optimal Algorithms for Approximate Clustering", Feder and Greene [1988] (https://dl.acm.org/doi/10.1145/62212.62255).
Specifically, I was trying to look at the $1.82$...
- 13
0
votes
1
answer
100
views
On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)
Introduction
I am currently studying chapter 17 (of the famous textbook by Arora & Barak [1]) on the complexity of counting and got stuck on the proof of Lemma 17.7, which states $\mathrm{PP} = \...
- 173
0
votes
0
answers
54
views
Polynomial GCD exact complexity in terms of degree and number of variables
https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials states multivariate polynomial GCDs may be defined over $\mathbb F_p[x_1,x_2,\dots,...
- 12.6k