Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
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, ...

1
2 3 4 5
56