Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
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 ...
Tulasi's user avatar
  • 327
8 votes
0 answers
110 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$.&...
Siddharth's user avatar
  • 803
0 votes
0 answers
132 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^...
Nicholas Brandt's user avatar
7 votes
1 answer
319 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 ...
M A's user avatar
  • 215
6 votes
1 answer
286 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$-...
Reijo Jaakkola's user avatar
0 votes
0 answers
96 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 \...
Noel Arteche's user avatar
7 votes
1 answer
261 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 ...
gen's user avatar
  • 260
0 votes
0 answers
55 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) ...
Nicholas Brandt's user avatar
1 vote
0 answers
72 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 ...
Turbo's user avatar
  • 12.8k
2 votes
0 answers
107 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 ...
AITOR GODOY's user avatar
12 votes
1 answer
2k 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 ...
a3nm's user avatar
  • 8,916
2 votes
0 answers
113 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 ...
Mathieu Mari's user avatar
0 votes
0 answers
73 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 ...
Krish Singal's user avatar
5 votes
0 answers
163 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)$ ...
Joshua Grochow's user avatar
2 votes
0 answers
89 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 ...
Krish Singal's user avatar
5 votes
2 answers
255 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 ...
Lê Thành Dũng Nguyễn's user avatar
1 vote
0 answers
103 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 ...
Andras Farago's user avatar
0 votes
1 answer
105 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 ...
qc6518's user avatar
  • 1
0 votes
0 answers
79 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. ...
Student's user avatar
  • 127
2 votes
0 answers
39 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 ...
user76284's user avatar
  • 652
3 votes
3 answers
458 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 ...
user1868607's user avatar
2 votes
1 answer
66 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 ...
Dmytro Taranovsky's user avatar
0 votes
0 answers
57 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, ...
Lycus's user avatar
  • 101
7 votes
0 answers
159 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 ...
1110101001's user avatar
2 votes
0 answers
112 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 ...
ddr's user avatar
  • 21
1 vote
0 answers
20 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$ ...
Zach Hunter's user avatar
0 votes
0 answers
121 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 ...
gdoug's user avatar
  • 101
4 votes
0 answers
320 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 ...
Spencer Compton's user avatar
2 votes
0 answers
77 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....
Turbo's user avatar
  • 12.8k
-1 votes
1 answer
113 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 ...
ryu576's user avatar
  • 109
0 votes
0 answers
91 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 ...
Turbo's user avatar
  • 12.8k
6 votes
1 answer
309 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$...
Agile_Eagle's user avatar
0 votes
1 answer
116 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} = \...
sebastian's user avatar
  • 173
0 votes
0 answers
60 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,...
Turbo's user avatar
  • 12.8k
0 votes
0 answers
72 views

Interactive proofs with computation bounded Merlin

Consider usual interactive proofs (Arthur is polynomial-time bounded and can use random bits) where computation power of Merlin is bounded by polynomial-size circuits. For example, every unary NP-...
Alexey Milovanov's user avatar
1 vote
2 answers
82 views

Examples of promise search problems that are easier than their non-promise variants?

By promise search problem, I mean a search problem for which the solution is guaranteed to exist (e.g. find a solution to a linear system of equations, knowing that a solution does exist). Are there ...
CSSTUDENT's user avatar
  • 219
3 votes
2 answers
291 views

Classes between PH and PSPACE

I am interesting in languages of the following form: $x \in L \Leftrightarrow Q y_1 Q y_2 \ldots Q y_n P(x, y_1, \ldots y_n, x).$ Here every Q is $\forall$ or $\exists$; $n$ is the length of $x$, the ...
Alexey Milovanov's user avatar
1 vote
1 answer
72 views

Running time of SAT and other EXPTIME algorithms [closed]

I need to propose an algorithm for a NP-hard problem. I use dynamic programming which leads to a running time $O(2^s\cdot n^2), s\leq n.$ The algorithm aims to finding a path in a graph $G(V, E)$ (in ...
user67418's user avatar
1 vote
1 answer
170 views

Complexity of "discrete-time" SAT

I'm interested in the complexity of deciding satisfiability of the following family of formulae: $\exists j. I[j(0)] \land \forall t. S[j(t),j(t+1)]$ where: $j:\mathbb{N} \to \{0,1\}^n$ has finite ...
user1868607's user avatar
2 votes
1 answer
314 views

Is any computational complexity question solved by injury priority method except Post problem?

As we know, there are many questions of Turing Degree closed by injury priority method. Is any computational complexity question solved by injury priority method except Post problem or Turing Degree? ...
XL _At_Here_There's user avatar
3 votes
0 answers
74 views

Solving MDPs with polytope action spaces

A (finite) Markov Decision Process (MDP) consists of a finite set of states $S$, a finite set of actions $A_s$ which we will allow to depend on the state $s\in S$, an initial state $s_0\in S$ (the ...
Vanessa's user avatar
  • 2,151
0 votes
1 answer
217 views

What Complexity Class is this? Is this already known?

Let's call this the Path Game. For this example, lets imagine a 16x16 grid: Some of the squares in this grid are "deadly." If you step on it, you must restart and try to go over again. We ...
Bapcap's user avatar
  • 21
-1 votes
1 answer
153 views

Cook's theorem and universal machine

From Papadimitriou and Yannakakis, "A Note on Succinct Representations of Graphs" second parragraph of the proof of the main result. Cook (1971) presented in his classical paper a ...
user1868607's user avatar
4 votes
0 answers
138 views

(PCP theorem) Any natural decision problem defined in the format of PCP-verifiers?

Is there any natural decision problem that "trivially fits" the definition of a PCP-verifier? I mean, a problem precisely defined as follows: given a set of constraints (each one depending ...
EXPTIME-complete's user avatar
-1 votes
1 answer
85 views

Is logic in computation of computation constructivist?

Is logic in computation of computation constructivist? I think so, because dynamic languages ​​are comparable to constructivist set theory (try a demonstration of the axiom of choice in computing: it ...
Lambert macuse's user avatar
4 votes
0 answers
148 views

What is the intuition behind P/qpoly=P/poly?

I very much struggle to understand the qualitative differences between anything/qpoly. For exampe we read at Watrus that BQP/qpoly essentially are the decision problems that are solved by polynomial ...
Marion's user avatar
  • 183
0 votes
1 answer
177 views

Information theoretic arguments for complexity

This Wikipedia article,Decision tree model, states that decision tree complexity lower bound $O(n \log_2 n)$ for sorting problem is information theoretic since any algorithm ( modeled as decision ...
Mohammad Al-Turkistany's user avatar
2 votes
0 answers
106 views

Gurevich's theorem on primitive recursive functions being logspace-computable

I recently came across the following result attributed to Gurevich, according to which I understood that the class of problems solvable by primitive recursive functions is precisely the class L of ...
Noel Arteche's user avatar
1 vote
0 answers
142 views

Looking for an implementation of any PCP-verifier for any NP problem

Is there any implementation of any PCP-verifier (for any NP problem) researchers can download and test? No matter if it is a github entry with actual downloadable code or just a (reasonably detailed) ...
EXPTIME-complete's user avatar
2 votes
0 answers
94 views

Finding Hamilton cycles in random graphs

For a random graph $G$ of minimum degree 3, can we find a Hamilton cycle in linear time (with high probability for every edge density)? If this is an open problem, I will also accept an empirically ...
Dmytro Taranovsky's user avatar

1 2
3
4 5
61