Skip to main content

Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
1 vote
0 answers
32 views

Clause Density for guaranteed Easy (2, 3) SAT Cases

It is known that its NP-Complete to decide the satisfiability of 3-SAT instances in which every variable occurs four times. Now given a (2, 3)-SAT instance where each clause has length 2 or 3. ...
TheoryQuest1's user avatar
3 votes
1 answer
77 views

Solving #SAT through TQBF

I'm not extremely proficient with counting complexity classes, but since #SAT is #P-complete, its decision version, let's call it #SAT(D) (is the number of solutions less than some $k$), is in PSPACE. ...
Nicola Gigante's user avatar
2 votes
1 answer
127 views

Complexity of 2-coloring with extra constraints

I am considering the following problem: Given a graph $G=(V,E)$ with $|V|=4n$ vertices, can we color the vertices in two colors (red and blue) with The usual constraint that two vertices connected by ...
Jun_Gitef17's user avatar
4 votes
0 answers
59 views

EXPSPACE-complete optimization problems

This is similar to this question but specifically for optimization problems. Which are some optimization problems that (have corresponding decision problems that) are EXPSPACE-complete?
Nicola Gigante's user avatar
1 vote
2 answers
143 views

Use of transitive closure in proof of NC hierarchy collapse

Im looking at the proof of $NC^{i} = NC^{i+1} \implies NC = NC^i,\,i\geq 1$ in page 10 of the following article: https://www.cs.uoregon.edu/Reports/TR-1986-001.pdf I understand the general idea ...
Hlkwtz's user avatar
  • 11
3 votes
0 answers
48 views

Complexity of minimizing the index of a subgroup of the free group

Let $\Sigma$ be a finite alphabet and $G$ the free group generated by $\Sigma$. Let $W$ be a finite subset of $G$. (Represented as a list of formal expressions of the form $a_1^{\pm 1}\ldots a_n^{\pm ...
Vanessa's user avatar
  • 2,181
2 votes
1 answer
68 views

Hardness of the Metric TSP for the Maximum Metric

I know that it is not too difficult to construct a metric to show that the metric TSP is NP-hard. The typical example is (1,2)-TSP. I also know that Papadimitriou has shown that Euclidean TSP is NP-...
jfriemel's user avatar
1 vote
0 answers
34 views

On the Relationship Between Graph Isomorphism and Equivalence in ETL Workflow Dependency Graphs

Let $G = (V, E)$ and $G' = (V', E')$ be two DAGs representing dependency graphs of ETL workflows. Each node $v \in V$ (or $v' \in V'$) represents a task, which is a tuple $t_v = (q_v, d_v, s_v)$, ...
Zoom's user avatar
  • 11
2 votes
1 answer
103 views

On the power of QMA(2)

I searched for references. But I could not find any. Is $EXP\subseteq QMA(2)$ known?
user72910's user avatar
1 vote
0 answers
112 views

Efficient algorithm to construct simple polygon from non-crossing orthogonal line segments

Given a set of $N$ non-crossing orthogonal (vertical and horizontal) line segments on the plane, is there an efficient algorithm to construct a simple orthogonal polygon that passes through all given ...
Mohammad Al-Turkistany's user avatar
5 votes
1 answer
124 views

How to prove that a problem is not smoothed-polynomial?

Many research works use Smoothed analysis to prove that some NP-hard problems can actually be solved efficiently in typical cases. A different notion with a similar goal is Generic-case complexity. ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
126 views

Where does a problem lie which is NP-hard but not QMA-hard?

I saw this complexity classes diagram in this quantum computing paper in NATURE. Based on the standard assumption of $P\neq NP\neq QMA$, they also seem to have related the NP-hard and QMA-hard ...
Manish Kumar's user avatar
0 votes
0 answers
79 views

Evidence extended GCD is in $TC^0$

Despite centuries of search extended $GCD$ is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes ...
Turbo's user avatar
  • 13.1k
4 votes
1 answer
103 views

Smoothed analysis in the Turing machine model

Smoothed analysis is usually defined using real numbers: given $n$ and $\sigma$, the smoothed runtime of an algorithm is the maximum, over all inputs of size $n$, of the runtime on the input when it ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
129 views

$P^{\#P}$ complete problems

Are there any known $P^{\#P}$ complete problems? The problem would have to be at least as hard as anything in the polynomial hierarchy, but perhaps not as hard as PSPACE
BeniBela's user avatar
  • 101
0 votes
0 answers
58 views

Non-linearly ordered hierarchy of classes between NP and NEXP

I'm interested in the hierarchy of complexity classes between NP and NEXP. I have asked before about this Hierarchy of classes between NP and NEXP and found that already the time hierarchy theorems ...
user1868607's user avatar
  • 1,049
4 votes
1 answer
133 views

Constructing vector valued boolean circuits from boolean circuits

This is a reference request. I'm interested in the compositional construction of small boolean circuits for vector-valued boolean functions $\phi : \mathbb{B}^m \rightarrow \mathbb{B}^n$ for $n >...
Martin Berger's user avatar
2 votes
0 answers
161 views

Searching for a proof that non-deterministic logspace with errors is contained in $PL$

In this 10 year old question Non-deterministic logspace with two-sided error the author asked for a complexity class related to $NL$. Namely $NL$ but we are allowed to have two-sided error for the ...
user0001's user avatar
4 votes
1 answer
80 views

Reference request: finite field computation over the Word-RAM model

Let $q = p^\ell$ be a positive integer power of a prime $p$, of size $q = \text{poly}(n)$. Over the Word-RAM model (with words of size $O(\log n)$), how quickly can we perform addition and ...
Naysh's user avatar
  • 686
6 votes
1 answer
300 views

How stringent is the peer review process of ECCC exactly?

Apologies for the soft question. ECCC (the Electronic Colloquium on Computational Complexity), on its website (ECCC), says it is a compromise between the negligible peer review of ArXiv and the long ...
Tejas's user avatar
  • 369
0 votes
0 answers
63 views

Resolution lower bound for pigeonhole principle when placement clauses are shortened

Consider the standard CNF encoding of pigeonhole principle $PHP_{n}^{n+1}$: $$ \text{Placement clauses: } x_{i,1} \lor x_{i,2} \lor \cdots \lor x_{i,n} \forall i \in [n+1] $$ $$ \text{Collision ...
aba's user avatar
  • 91
0 votes
1 answer
133 views

Hierarchy of classes between NP and NEXP [closed]

Ladner's theorem shows that if $P$ is different from $NP$ then there are actually infinitely many complexity classes (for polynomial time reducibility) between the two. I was wondering if this is also ...
user1868607's user avatar
  • 1,049
2 votes
1 answer
86 views

Time Complexity of KnuthBendixCompletion Algorithm [closed]

I am currently studying the Knuth-Bendix completion algorithm and trying to understand the factors that contribute to its time complexity. This algorithm is used to transform a set of rewrite rules ...
Navvye's user avatar
  • 21
6 votes
0 answers
131 views

Is there a known correlation between the Strong Exponential Time Hypothesis (SETH) and the existence of one-way functions?

It is known that (one-way functions exist $\implies$ $\textbf{P}\neq \textbf{NP}$) and as far as my knowledge goes, the converse is not known to be true. Are there any known results correlating $\...
Tejas's user avatar
  • 369
6 votes
0 answers
142 views

Proof complexity of Sudoku

Let $P$ be a $N$x$N$ Sudoku puzzle (assume $N=n^2$ for some $n\in \mathbb{N}$, e.g. standard $9$x$9$ puzzle is $n=3$). We can represent it in propositional logic as follows: Variables $p_{i,j,k}$: ...
Kaveh's user avatar
  • 21.7k
4 votes
1 answer
144 views

Intersection Non-Emptiness for Two-Way Finite Automata

We know that checking the emptiness of intersection of an unbounded number of deterministic finite automata is PSpace-complete, and that just the emptiness problem for a nondeterministic two-way ...
A. G.'s user avatar
  • 43
5 votes
3 answers
212 views

Why is order/choice an issue for a logic for PTIME

As I'm reading on the question of a logic for PTIME and in particular about CPT and its variants, whilst things make sense and I follow along, I came to realise that I don't fundamentally understand ...
Matei Chesa's user avatar
4 votes
0 answers
98 views

Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?

We know that $\mathsf{BPP}$ is in $\mathsf{\Sigma^P_2\cap \Pi^P_2}$ by Sipser-Lautemann, as this proof relativizes we can get $\mathsf{BPP^{NP} \subseteq \Sigma^P_3\cap \Pi^P_3}$, but are there any ...
Marsh's user avatar
  • 41
0 votes
0 answers
86 views

Proof of coNE ⊆ NE/poly

I'm finding it hard proving that NE/poly contains coNE which is backed by Complexity Zoo. It states that we can use the proof for NEXP/poly containing coNEXP but the link to the reference paper ...
rock_lee's user avatar
0 votes
0 answers
49 views

On a modular inverse graph construction

Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
Turbo's user avatar
  • 13.1k
2 votes
0 answers
70 views

On mod $p$ constructions related to determinant

Given an $m\times m$ matrix $M\in\mathbb Z^{m\times m}$ and a prime $p$, is it possible to construct in $Logspace$ another matrix $t_1(M)$ whose determinant is guaranteed to be determinant $Det(t_1(M))...
Turbo's user avatar
  • 13.1k
3 votes
0 answers
54 views

Hardness of deciding fractional chromatic number at most $k$

I want to find a reference for the following statement. Here, $\chi_f(G)$ denotes the fractional chromatic number of a graph $G$. For every fixed $r>2$, deciding $\chi_f(G) \leq r$ for a given ...
Minsoo Kim's user avatar
3 votes
0 answers
65 views

Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

I have 2 type of decision problems: either in $\mathsf{BPP}$ or in $\mathsf{NP}$; and I want to decide fixed Boolean combinations of them. Since $\mathsf{BPP}$ is closed under Boolean combinations and ...
DiegoEmilio's user avatar
2 votes
0 answers
89 views

Evidence for $\oplus P\subseteq\#P$ and barriers to proving it

Is there evidence that $\oplus P\subseteq\#P$ and evidence towards $\oplus P\not\subseteq\#P$ ? We know $\oplus P\subseteq FP^{\#P}$ What are some barriers to proving this inclusion $\oplus P\subseteq\...
Turbo's user avatar
  • 13.1k
0 votes
0 answers
58 views

Why can't we just reduce from Bounded HALT to Bounded PCP?

We know that: PCP is famously undecidable (as it can encode any DTM), but Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and Bounded-PCP (there is a matching ...
apirogov's user avatar
  • 101
1 vote
0 answers
159 views

Relation between $k$-sum failure and $P=NP$

If $P=NP$ then $W[1]=FPT$ holds. Hence $k$-sum conjecture fails at a finite $k$. What can we say about the time complexity of $SAT$ and the lowest $k$ at which $k$-sum conjecture fails? In particular, ...
Turbo's user avatar
  • 13.1k
0 votes
0 answers
59 views

Complexity of LSB and MSB of Diffie-Hellman

Given generator $g$ of multiplicative cyclic group modulo $p$ a prime and two elements $h_1$ and $h_2$ such that there are $x_1$ and $x_2$ respectively satisfying $g^{x_i}=h_i\bmod p$ at every $i\in\{...
Turbo's user avatar
  • 13.1k
1 vote
0 answers
70 views

Why is the model-checking problem for MSO $\textsf{PSPACE}$-complete?

I am currently reading "Parameterized Complexity Theory" by J. Flum and M. Grohe. In Chapter 10.3 they state in the first paragraph: Let us remind the reader that the model-checking problem ...
user11718766's user avatar
0 votes
0 answers
72 views

Reductions That Acts on Witnesses

We say that a language $X$ is polynomial time reducible to $Y$, intuitively, if given an algorithm for solving $Y$, there's an algorithm for solving $X$. I know this can be formalized using Karp ...
Boran Erol's user avatar
2 votes
0 answers
106 views

Constructing complex languages without "recursion"

I'm curious of the ways we can construct provably complex languages. In particular, most constructions (i.e., the one used for proving the Time hierarchy theorem) seem to rely on encodings of Turing ...
mti's user avatar
  • 117
-1 votes
1 answer
55 views

Computability/Complexity of optimization problems in general

Dear StackExchange community, I have a question, or better phrased I am confused and would like to be enlightened by you! So assume we have a (optimization) problem like that: Instance: Let $f:\...
Thinklex's user avatar
4 votes
0 answers
158 views

Is there a 'mathematical program' to separate P from BQP?

This question has been motivated by the existence of an ongoing (and possibly long-term) program for $P\neq NP$ conjecture like GCT(Mulmuley, 1999). Usually, such programs are marked by long and ...
Manish Kumar's user avatar
1 vote
0 answers
89 views

What would be the cost to factor a 1024‒bits RSA modulus most economically within months today?

Of course this is a question with an answer that is due to evolve. A 2002 paper about TWIRL stated that the cost would be around 10M$$ and an other 10M$ to manufacture the devices. A later 2007 paper ...
user2284570's user avatar
-3 votes
1 answer
157 views

The most complex language? [closed]

I'm interested in understanding the complexity of languages. If I wanted to construct a language that is very difficult to decide, how would I go about this? Is it known whether we can artificially ...
mti's user avatar
  • 117
7 votes
0 answers
107 views

Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned: Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ ...
user11718766's user avatar
1 vote
0 answers
107 views

Why does the Time Hierarchy Theorem fail relative to promise problems?

Define Program Evaluation (PE) to be the promise problem of determining whether a program (written in a Turing-complete language) returns True or False. The promise is that the program will return ...
Demi's user avatar
  • 528
8 votes
0 answers
297 views

Is GCT still active?

Is Mulmuley's geometric complexity theory program still active? I tried to look it up online, and I haven't seen anything from the last couple of years.
domotorp's user avatar
  • 14.1k
2 votes
1 answer
224 views

Research masters programs in theoretical computer science (with a focus on complexity theory)

I am in my 2nd year of my Computer Science degree. I am deeply interested in Complexity Theory, and I plan to pursue a career in this field I am from South Asia, and research here is not up to par, ...
FooFighter39's user avatar
0 votes
0 answers
39 views

converting K-SAT clause to a p-in-L-SAT equation

Given a generic K-SAT instance $S$ with $n$ boolean variables. Is it possible to convert a clause of this instance into an equivalent p-in-L SAT system of equations such that the number of new clauses ...
TheoryQuest1's user avatar
4 votes
0 answers
83 views

Uniform lower bounds in terms of the matrix multiplication exponent $\omega$?

Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is ...
Mingda Qiao's user avatar

1
2 3 4 5
62