Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,778
questions
-3
votes
0answers
54 views
Is there a concept of probabilistic quantum computers?
Answering my question Are there computable functions of quantum time complexity strictly above polynomial? Yonatan N said a statement from which follows that there are computable functions of quantum ...
-2
votes
0answers
58 views
Are there computable functions of quantum time complexity strictly above polynomial?
Is there a known proof that there are computable functions of quantum time complexity strictly above polynomial?
Can you point to a reference, such as a Wikipedia article?
-2
votes
0answers
38 views
Proof that there are computable functions of time complexity strictly above polynomial
Sorry, for a quite stupid question:
Is there a known proof that there are computable functions of time complexity strictly above polynomial?
Can you point a reference, such as a Wikipedia article?
2
votes
0answers
56 views
Improving the approximation in Stockmeyer's counting theorem
Given a $\#P$ function $f(x)$, we can use Stockmeyer's counting theorem to get an approximation $g(x)$ such that
\begin{equation}
\left(1 - \frac{1}{\text{poly}(n)} \right) f(x) \le g(x) \le \left(...
-5
votes
0answers
73 views
Does a nondeterministic TM have different definitions of termination for computability and complexity? [closed]
In Sisper's Introduction to Theory of Computation, Section 3.2 VARIANTS OF TURING MACHINES says
The computation of a nondeterministic Turing machine is a tree whose branches
correspond to different ...
1
vote
1answer
48 views
Amortized time and worst case (non-amortized) separation
Assume a reasonable computation model (thinking about pointer machine or RAM model), is there a problem where there is a clear separation between amortized and worst case complexity? Say, if ...
0
votes
0answers
98 views
Bigger collapse and Savitch's theorem?
Let $L^t=DSPACE[O(\log n)^t]$, $NL^t=NSPACE[O(\log n)^t]$ and $UL^t=USPACE[O(\log n)^t$.
Savitch provides $NL\subseteq L^{2}$.
If $P$ or $CH$ is in $\oplus L$ or $C_=L$ or $UL$ or $NL$ or their ...
1
vote
0answers
43 views
A proved computationally-irreductible function
In arXiv:1111.4121 and arXiv:1304.5247, Hervé Zwirn and Jean-Paul Delahaye propose a formal definition of computational irreducibility. Is there a (possibly artificial) function that can be proved to ...
-1
votes
0answers
49 views
Where is the following function in?
If a boolean function is in $UL\cap\mathsf{monotoneAC}^1$ and can be captured by evaluation problem of a circuit which is an $AND$-$OR$ circuit of $O(\log n)$ depth where $AND$ fan-in is $2$ and $OR$ ...
-4
votes
0answers
113 views
Is an abstract machine stateful? [closed]
In theory of computation, https://en.wikipedia.org/wiki/Abstract_machine says
An abstract machine, also called an abstract computer, is a theoretical computer used for defining a model of ...
3
votes
1answer
109 views
What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?
It is known $AC^0[2]$ cannot get majority function.
Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$?
What is ...
4
votes
1answer
124 views
Is $GCT$ necessarily a negative result program?
$GCT$ is a candidate program to separate permanent and determinant through symmetries. If indeed permanent and determinant can be handled in similar complexity class would $GCT$ be a program which can ...
1
vote
0answers
69 views
Algorithms for finding unique solutions of NP-complete problems
The complexity of algorithms that find unique solution for an NP-complete problem (the input is guaranteed to have a unique solution) seems to shed light on the hardness character of different NP ...
-2
votes
0answers
44 views
$\mathsf{NP}$-complete reduction efficiency and $\mathsf{NP}$-completeness of subexponential subsets of $\mathsf{NP}$ complete problems
Let $f:\{0,1\}^n\rightarrow\{0,1\}^m$ be from the family of functions $\mathcal F_{n,m}$ parametrized by lengths $n,m$. It is to say $f\in\mathcal F_{n,m}$ and let the cardinality of $\mathcal F_{n,m}$...
1
vote
1answer
136 views
Pursuing Theoretical Computer Science after CS major
So I am currently a sophomore majoring in Computer Science. In the Data Structures course that I am currently studying, I studied the basics of complexity of a program and big O-notation, etc. That ...
9
votes
1answer
178 views
Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?
The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ ...
4
votes
0answers
137 views
The graph of problem reductions
A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
-4
votes
0answers
38 views
TISP tradeoff bounds for $C$-uniform $TC^0$?
Let $C$-uniform $TC^0(n)$ be the class of functions computable by a $TC^0$ circuit of size $n$, where $C$ is DLOGTIME, LOGSPACE, or PTIME.
Is there a time-space $\mathrm{TISP}(t(n),s(n))$ bound for ...
3
votes
0answers
105 views
PSPACE-complete under NP reduction
Is there some example of a PSPACE problem that we can show PSPACE-hard under NP reduction, but we do not know a proof of PSPACE-hardness under P reduction ?
To be more precise, the NP reduction I am ...
0
votes
1answer
129 views
Comparing SAT to MCSP reduction class separations and faster SAT class separations?
Assume $SAT$ is in $QuasiP$. We immediately infer $NQuasiP=QuasiP$ and $EXP=NEXP$. From https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf we infer $NQuasiP$ is not in $P/poly$ which implies $...
0
votes
0answers
68 views
What is the best reduction we know from flavors of $SAT$ to $MCSP$?
Consider $\mathcal P(n,m)$ to be a class from the set $\{k\mbox{-}\mathsf{SAT}(n,m),\mathsf{CIRCUITSAT}(n,m)\}$ where $k$ is fixed, $n$ is number of variables and $m$ is number of clauses.
Denote $\...
1
vote
0answers
22 views
Clauses structure as quenched random matrix for random $k$-SAT problems
In the Section III of Statistical mechanics of the random K-SAT model, the clauses structure of random $k$-SAT problems are expressed as $M \times N$ quenched random matrix where the numbers of ...
0
votes
0answers
25 views
Which algorithm for linear programming is suitable for the context of quantum computing?
There are two major types of algorithms for linear programming : extreme point based, interior point based.
Which will be suitable for quantum computing?
4
votes
0answers
88 views
Relationship between SC and NL
It is a major open problem whether $NL \subseteq SC$, or equivalently, whether directed reachability can be solved (simultaneously) in poly-logarithmic space and polynomial time. What is known ...
0
votes
0answers
47 views
Size of CNF Formula for Adjacency in Configuration Graph
Suppose $M$ is a (non-deterministic) TM that runs in space $S(n)$. Then, the configuration graph $G_{M,x}$ of $M$ on $x$ has size $2^{O(S(n))}$. Arora-Barak (see http://theory.cs.princeton.edu/...
3
votes
2answers
125 views
Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals [closed]
Looking for some lecture videos (introductory level) on logic, models of computation as well as computational complexity/ other theoretical computer science fundamentals
0
votes
0answers
106 views
$\mathsf{ACC}^0$ and $\mathsf{TC}^0$ with $\mathsf{Cuniform}$-$\oplus\mathsf{L}$ or $\mathsf{Cuniform}$-$\mathsf{NC}^1$ oracle?
$\mathsf{TC}^0$ is a small class with $\oplus\mathsf{L}$ containing it.
Following inclusions are known:
$$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\...
3
votes
0answers
88 views
Increasing Functions in Non-deterministic Time Hierarchy Theorems
I was going over the proofs of the non-deterministic time hierarchy theorem (the one in Arora-Barak and the one by Fortnow and Santhanam). They are available here:
http://theory.cs.princeton.edu/...
0
votes
0answers
4 views
Is base conversion in $\mathsf{TC^0}$?
$\mbox{Problem}_{j,i,q}(x_1,\dots,x_n)$: Given an integer $\sum_{i''=0}^{n-1}2^{i''}x_{i''+1}$ in binary output the $j$th binary digit of the $i$th base-$q$ digit (where $q$ is not necessarily a prime)...
2
votes
1answer
109 views
Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$? [closed]
A complete problem for $\mathsf{PPP}$ is the pigeon problem which is 'Given a Boolean circuit ${\displaystyle C}$ having the same number ${\displaystyle n}$ of input bits as output bits, find either ...
-2
votes
0answers
49 views
On the boolean complexity and complexity class of Diophantine equations with non-negative bounded solutions
Given $f(x_1,\dots,x_m)\in\mathbb Z[x_1,\dots,x_m]$ of total degree $d$.
Denote by $\|f(x_1,\dots,x_m)\|_\infty=T$ the maximal absolute value coefficient of $f(x_1,\dots,x_m)$.
Is there an $\omega\...
5
votes
1answer
210 views
Is there a containment between $\mathsf{ZPP}$ and $\mathsf{UP}$?
Do we know if $\mathsf{ZPP}\subseteq\mathsf{UP}$ known or is there oracles against the hypothesis?
32
votes
12answers
5k views
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below:
The original algorithms,...
2
votes
0answers
48 views
Does the awards budget cut problem support a sub $O(n\log n)$ time solution?
There's a famous problem these days in the interview prep community (particularly in PRAMP) called the awards budget cut problem.
The problem gives you an input of $n$ integers called grants $g_1 ... ...
1
vote
0answers
29 views
Complexity Lower Bounds for 3D Sparse Gaussian Elimination
I'm interested in lower bounds on the complexity in the real-RAM model of solving systems of linear equations which have the sparsity pattern of a three-dimensional cubic mesh. Specifically, consider ...
-4
votes
1answer
22 views
Help find algorithm for array-based task
Given array if numbers a[1..n]. Pair of numbers (i, j) is interesting, if i < j и a[i] > 2a[j]. How to count number of interesting pairs in O(nlogn)?
What is the solution?
My solution is not ...
12
votes
0answers
324 views
NP complete problem help
I'm currently trying to find a reduction to this problem:
Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
1
vote
0answers
60 views
Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains
Let ${\cal L}=\{Y_1,..., Y_k, X\}$ be a finite relational language such that $X$ is a unary relation name. Let $\phi(X,\bar{Y})\in{\cal L}$ be a first-order formula (the formula can have the equality ...
1
vote
0answers
205 views
Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?
Underlying motivation for the question: if someone showed that $\text{P}=\text{NP}$ but the algorithm thus produced for, e.g., $3\text{-SAT}$, runs in time $\Omega(n^G)$ where $G$ is Graham's number, ...
2
votes
0answers
45 views
Computational complexity problem book with solution recommendation?
I will be taking complexity class next quarter and we will use the book "B. Barak, S. Arora, Computational Complexity: A Modern Approach". However, I have little exposure to complexity ...
10
votes
0answers
136 views
Provable BPP Hierarchy
No Time Hierarchy theorem is known for $\mathsf{BPTIME}$, however, consider the following simple modification of the definition:
A language is in $\mathsf{ProvableBPTIME}[f(n)]$ if there is a ...
5
votes
2answers
244 views
Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?
Since $e$ is transcendental, the function $f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$ is injective,
$$ f(\underset{\text{Integers}\ \geq\ 0}{\underbrace{a_0,a_1,\ldots, a_n}}) = a_0 + a_1e+a_2e^2+\cdots ...
1
vote
0answers
45 views
Living in Minicrypt, but sampling hard instances without the solution
In Impagliazzo's worlds, Minicrypt is the one, where one way functions exist.
In other words, we can sample hard-on-average instances of NP complete problems.
Question:
Is living in Minicrypt, where ...
1
vote
1answer
100 views
Complexity of a satisfiability problem
I would like the know the complexity of a specific satisfiability problem. I have a feeling it could be solved in polynomial time, but I am not sure about it. The problem is described below.
Given $n$ ...
2
votes
1answer
110 views
Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses?
Let $\phi$ be negative monotone 2-CNF on $n$ variables and $n^{3/2}$
clauses.
What is the complexity of finding satisfying assignment with maximum
number of ones $k$?
Alternatively let $G$ be a graph ...
3
votes
0answers
131 views
If $\sf{E} = \sf{NE}$. Then $\sf{NP}-{P}$ contains no sparse sets [closed]
I am reading "The Complexity Companion" by Hemaspaandra & Ogihara, I have a question about lemma 1.21.
In its proof, they suppose $L$ is some sparse language in $\sf{NP}$ ($||L^{=n}||&...
22
votes
2answers
2k views
Is Descriptive Complexity dead?
I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be ...
0
votes
0answers
46 views
Balanced and general $MAXkSAT$ known approximation results and bounds from $UGC$
$MAX2SAT$ has a $0.9401$ to $0.9402$ approximation algorithm which is conjectured to be optimal by $UGC$ while there is a balanced $MAX2SAT$ bound of $0.943$ approximation which is conjectured to be ...
6
votes
1answer
204 views
Are all computational models of quantum computing equivalent?
So the question was inspired by a seminar which presented the following models of quantum computing:
Quantum Computing with Photons
Quantum Computing with Rydberg atoms
Quantum Computing with trapped ...
0
votes
0answers
80 views
Is the traveling salesman problem still NP-hard if all edges need to be covered as well?
If we formulate the travelling salesman problem with an added edge-covering constraint as follows, is it still NP-hard?
Given a graph G with non-negative edge weights, is there a circular walk in G ...
