Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,788
questions
3
votes
0answers
51 views
Useful notion of ambiguous growing context-sensitive language
As far as I understand there is no useful notion of ambiguous context-sensitive language.
For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating ...
2
votes
0answers
187 views
The implication of $ S(SAT)=2^{\Omega{(n)}} $ Conjecture (5.7 in Wigderson Book)
I started to read Avi Wigderson book Math and Computation, which get me excited about the following:
Conjecture 5.7. $
S(SAT)=2^{\Omega{(n)}}
$,
where $S$ denotes the size of the smallest Boolean ...
-3
votes
0answers
44 views
Reduction of CNF-SAT to 3-dominating set [closed]
I don't understand Lemma 2.1: http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf
"Suppose S has two (or more) partial assignment nodes from the same clique. Then there is some clique for ...
2
votes
1answer
35 views
Relative error estimation of a special type of GapP function
Consider the functions included in the complexity class GapP.
We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly ...
-3
votes
0answers
114 views
Are space and time hierarchies infitesimally graded?
Space(n) is in nspace(n) which is in space (n^2) and I get refinements in. https://en.wikipedia.org/wiki/Space_hierarchy_theorem#Refinement_of_space_hierarchy.
What is smallest f(n) so that space(f(n))...
3
votes
1answer
91 views
Hardness when restricted to an infinite number of far apart instance sizes
Is there a result that rules out (under common complexity theoretic assumptions) that one can solve an NP-hard problem in polynomial time for an infinite number of possibly very far apart instance ...
0
votes
0answers
74 views
Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$
Crossposted at MathOverflow
A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$. $\mathbf{1}$ is ...
-3
votes
0answers
91 views
When does complementariness imply lowness?
We know $NP=coNP$ implies $NP=PH$. However $PP=coPP$ does not imply $PP=CH$.
However $NL=coNL$ forbids $NL$ hierarchy. $PL=PL^{PL}$ has nothing to do with $PL=coPL$.
I. Why does $PP=coPP$ does not ...
0
votes
0answers
177 views
An $O(n^2\log^c{n})$ algorithm for matrix multiplication in this paper?
In the newest version of this paper by Yijie Han, the author claims that matrix multiplication can be solved by an $\tilde{O}(n^2)$ algorithm. It should be a big result, but it is still in arxiv and ...
-1
votes
0answers
184 views
What progress has been towards $ZPL=L$?
$BPL$ is in $SPACE(O(\log^2n))$ by derandomization result of Nisan which was improved to $SPACE(O(\log^{3/2}n))$ by Saks and Zhou and which was superceded by Hoza in eccc.weizmann.ac.il/report/2021/...
3
votes
1answer
233 views
Proof and computational complexity
I couldn't find documents elaborating on this: if the Curry Howard correspondence is to be interpreted as establishing a strong relation between proofs and programs, should there not be a strong ...
4
votes
1answer
196 views
Complexity of relaxed edge colouring
A (proper) $k$-edge colouring of a graph $G(V,E)$ is a function $f:E\to\{1,2,\dots,k\}$ such that adjacent vertices are mapped to different colours; that is, $f(e)\neq f(e')$ if $e$ and $e'$ are ...
1
vote
1answer
140 views
KRW Conjecture: separation of NC^1 and P
More than a real question this is a recap of something I have been studying. I hope someone will help me getting things straight, so any correction or thought about the following reasoning is more ...
0
votes
1answer
68 views
Given a partition and an element, find the subset that includes this element
I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am ...
1
vote
0answers
197 views
anything hinting that EXPTIME $\subseteqq$ PSPACE?
Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？
3
votes
0answers
90 views
Monomial Sparsity of Boolean Functions
Suppose you have some boolean function $f: \{-1,1\}^n \rightarrow \{-1,1\}$ with rational coefficients such that all degree 1 monomials of $f$ have a nonzero coefficient and the degree $n$ monomial ...
0
votes
0answers
46 views
Complexity of finding typing derivation trees
In type theories where type checking is decidable do we have estimates for how much time/space it takes to find a typing derivation tree of a valid typing judgment? Do any published references do this ...
4
votes
1answer
269 views
Can we efficiently convert from NFA to smallest equivalent DFA?
Definitions
For any automaton $X$, let $L(X)$ denote the language recognized by $X$.
For any language $L$, let $sc(L)$ denote the number of states in the smallest DFA $X$ such that $L = L(X)$.
...
4
votes
3answers
140 views
The complexity of LH with constant gap
Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue ...
1
vote
0answers
56 views
Additive error approximations of GapP functions
Consider a GapP function $g(x)$ for $x \in \{0, 1\}^{*}$. Consider an approximation $\tilde g(x)$ such that
\begin{equation}
\left|g(x) - \tilde g(x)\right| \leq \epsilon.
\end{equation}
Consider a ...
2
votes
1answer
127 views
DFSA and NFSA intersection problem
Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem.
For unbounded $k$ it is known the problem is $PSPACE$ ...
3
votes
0answers
75 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(...
1
vote
1answer
52 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 ...
1
vote
0answers
44 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 ...
3
votes
1answer
121 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
157 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
82 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 ...
1
vote
1answer
153 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
185 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
145 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 ...
3
votes
0answers
109 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
133 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
70 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
30 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
92 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
129 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
108 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
91 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
5 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
112 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 ...
5
votes
1answer
243 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
50 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
31 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 ...
-5
votes
1answer
23 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
333 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
61 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
210 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, ...
