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
53 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
3 votes
0 answers
83 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
117 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
69 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
  • 13k
4 votes
1 answer
97 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
126 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
-2 votes
0 answers
52 views

Connect(G,k)={G is an undirected graph and uncomplete graph to wich you can add at most k edges to make it a clicque) is NP-Complete?

I have a problem with one demostration. I easly was able to show that $Connect(G,k)$ is in NP, but i was unable to show that it is NP-hard. I tried to reduct in polinomial time Vertex Cover, ...
Fabrizio Tempo's user avatar
0 votes
0 answers
55 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
130 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
110 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 ...
tcs_enjoyer's user avatar
4 votes
1 answer
78 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
286 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
62 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
130 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
80 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
128 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
137 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
138 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
208 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
94 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
83 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
47 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
  • 13k
2 votes
0 answers
68 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
  • 13k
3 votes
0 answers
53 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
64 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
87 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
  • 13k
0 votes
0 answers
57 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
157 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
  • 13k
0 votes
0 answers
58 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
  • 13k
1 vote
0 answers
68 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
70 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
105 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
54 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
156 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
85 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
155 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
101 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
104 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
281 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
  • 14k
2 votes
1 answer
208 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
38 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
79 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
12 votes
2 answers
701 views

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Do we know any problem that satisfies the following criteria? It is polynomial-time solvable on trees. It is NP-complete when restricted to graphs of treewidth 2. The problem can be encoded only ...
Prafullkumar Tale's user avatar
0 votes
0 answers
96 views

Is there a Hidden subgroup problem in BQP but suspected not to be in NP?

Wikipedia lists HSP problems in abelian and non-abelian groups. So does the following (extensive) compedium. I searched and found none is a BQP-complete (or even BQP-hard) problem. There has been a ...
Manish Kumar's user avatar
1 vote
0 answers
69 views

Is there a succinct representation of factoring which remains computationally intractable?

I'm looking for a succinct version of the factoring problem: i.e. given integers N and k, does N have a prime factor less than k, but somehow the input takes exponentially fewer bits to input? Ideally ...
Hans Schmuber's user avatar
0 votes
0 answers
62 views

Undecidability of games with limited hidden state

Surprisingly, approximate win probability for one-player games with randomness and 3 bits of hidden state (in addition to non-hidden state; rational transition probabilities) is uncomputable. Question:...
Dmytro Taranovsky's user avatar
2 votes
0 answers
81 views

On The Complexity of Block-Interchange Distance for Binary Strings

The block-interchange distance problem is defined as finding the minimal number of subsequences swaps to apply to an input string to turn it into a desired string. It is a well studied tractable ...
Daniel García's user avatar
2 votes
1 answer
132 views

Approaches to fast matrix multiplication and their limits

Let $\omega$ be the smallest constant so that we can do matrix multiplication in complexity $n^{\omega+o(1)}$. I am wondering what are the known avenues which establish the non-trivial bound $\omega&...
Zach Hunter's user avatar
3 votes
1 answer
247 views

Complexity of determining whether the language of an P machine is empty

Suppose you are given a deterministic Turing machine and you are guaranteed it runs in polynomial time. What's the computational complexity of determining whether the language accepted by the machine ...
user1868607's user avatar
  • 1,049
5 votes
1 answer
369 views

How does one "understand" complexity theory?

There's a famous quote by Bob Thomason about Grothendieck that he tried to understand algebraic geometry whilst everyone else was super-fixated on trying to prove theorems. Complexity theory, as one ...
Tejas's user avatar
  • 369

1
2 3 4 5
62