Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

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

1
2 3 4 5
56