Skip to main content

Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
3 votes
1 answer
228 views

Operation on Sub-exponential Reduction

I have a question concerning the SERF-reducibility of Impagliazzo, Paturi and Zane and subexponential algorithms. My question is: is a composition of two SERF reductions a SERF reduction? Are there a ...
S. M.'s user avatar
  • 109
6 votes
1 answer
491 views

Is relation between BQP and QMA resolved?

BQP vs QMA is a Quantum analogy of P vs NP. I recently went through the below pre-print on the IACR (International Association for Cryptologic Research) webpage. $BQP\neq QMA$ [link] I find it ...
Manish Kumar's user avatar
7 votes
0 answers
114 views

Parameterized complexity of factoring

When multiplying integer numbers $A$ and $B$, one can use a 0-1 matrix to represent one of the multiplication steps. For example, given numbers (written in binary) $A=1101$ and $B=1011$ the matrix is: ...
rus9384's user avatar
  • 355
5 votes
1 answer
117 views

How to intuitively express the hardness of Minicrypt and Cryptomania?

My question is as stated in the title. To give an example of “intuitively express”, it’s like: we often say Algorithmica means “NP is easy”, Heuristica means “NP is hard on worst-case but easy on ...
Heda Chen's user avatar
  • 181
0 votes
0 answers
34 views

What’s the difference between P-computable distributions and P-samplable distributions?

$\newcommand{\calC}{\mathcal{C}} \newcommand{\calD}{\mathcal{D}} \newcommand{\calE}{\mathcal{E}}$ I have two questions and the first one is presented in the title. The second one is about the ...
Heda Chen's user avatar
  • 181
2 votes
2 answers
79 views

State machine classes with sub-exponentially growing model spaces

State machines are useful tools for system modelling. They allow for a compact visual notation of discrete systems and provide a formal model of them. However, reasoning about the correctness of an ...
stateMachineOperator's user avatar
12 votes
1 answer
921 views

Status of András Faragó’s (second) claimed proof that NP=RP

In 2020, András Faragó claimed to have proved that NP = RP (discussion; v1 of the paper); the paper was later retracted due to a counterexample to theorem 1. A few days ago, Faragó posted another ...
Jiak Kantang's user avatar
12 votes
1 answer
486 views

Trade-off for Barrington's theorem

Barrington's theorem states that any Boolean circuit made up of gates of fan-in $2$ and with depth $d$ can be transformed into an equivalent Branching Program of constant width (in particular, of ...
Michael Lampis's user avatar
3 votes
0 answers
91 views

What's the complexity of the "decision version" of counting the paths in a graph?

I learned that "counting the simple paths in a graph(whether directed or not)" is #P-Complete. I'm wondering what the complexity is for its decision version. Here are two types I'm ...
Wenhao Wu's user avatar
0 votes
0 answers
89 views

On mod $2^i$ $+$-reducibility of permanent

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
Turbo's user avatar
  • 13k
1 vote
0 answers
73 views

Properties of #P functions that a GapP function may violate

I want to show a specific GapP problem is likely not in #P, actually very closely related to this question in terms of the area of mathematics it is from: How can I show a Gap-P problem is outside #P ...
Matt Samuel's user avatar
0 votes
0 answers
58 views

Implications of NL $\subseteq$ BQL/poly

As far as I could see it's not known whether NL $\subseteq$ BQL/poly. Is it actually not known? If not, what would be the implications of the inclusion?
eunice.goudarzi's user avatar
3 votes
1 answer
91 views

Application of PCP and error correcting codes to LLMs?

Are there any interesting results in applying error correcting codes and ideas from PCP (Probabilistically Checkable Proofs) to improve the quality of large language models (LLM), or connecting them ...
Kaveh's user avatar
  • 21.7k
2 votes
0 answers
38 views

definition of P-samplable distribution that allows non-binary fractions

Arora and Barak (in chapter 18, on average-case complexity) define a polynomial-time samplable (or P-samplable) distribution $D$ (actually a family $\{D_n\}$, for each output length $n$) as having an ...
Shivaram Lingamneni's user avatar
0 votes
1 answer
143 views

Complexity of simplex method

What is the complexity of the simplex method in terms of Big O in the general case? I saw two variants: O(2^n) and O(2^(n+m)), where n is the number of variables and m is the number of constraints
Kitty's user avatar
  • 1
5 votes
0 answers
265 views

What's wrong with this $P \neq BPP$ proof?

I developed this simple argument while learning about the $BP$ operator and McCreight and Meyer's Union Theorem, however I cannot pinpoint where my error is. By the Union Theorem, there exists a total ...
trillianhaze's user avatar
2 votes
0 answers
76 views

Categorical consequences in practical algorithms outside type theory

Most of my exposure to using categorical results to design algorithms, is through modularity in functional programming. I am wondering whether there are examples where the proof of existence of ...
Ilk's user avatar
  • 920
2 votes
0 answers
83 views

Extending Karp Reductions of a Decision Problem to Cook Reductions of the Associated Counting Problem

It seems that most NP-complete decision problems have #P-complete corresponding counting problems, with many examples showing this and no known counterexamples. In Jerrums' lecture notes `Counting, ...
space_kale's user avatar
4 votes
1 answer
159 views

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

It's suspected that probabilistic complexity classes such as $\mathsf{RP}$ or $\mathsf{BPP}$ don't have complete problems. Of course, their promise counterparts have complete problems, but I am not ...
rus9384's user avatar
  • 355
3 votes
1 answer
189 views

How often can a clause cause a conflict?

This question is about DPLL+CDCL algorithms. How often can a clause cause a conflict? I want to use a specific algorithm. Assume a DPLL+CDCL SAT solver using a fixed variable order. Variables and unit ...
Russell Easterly's user avatar
8 votes
1 answer
486 views

What can we do with a generic oracle (as opposed to a random one)?

Let me first recall a few (lengthy but hopefully mostly standard) facts and definitions in order to motivate my question (feel free to skip down to the actual question): Standard definitions: A ...
Gro-Tsen's user avatar
  • 841
1 vote
1 answer
178 views

Are there any algorithms that the brain is better at solving than a regular computer? How would these be found/verified?

For example, one that brains appear to be able to solve in polynomial time but computers can't, or one optimized for the brain's innate capabilities - like language learning, or different ...
soairse's user avatar
  • 11
2 votes
0 answers
86 views

Crafting ${NP}^{\#P}$-complete problems

Some related posts: Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$? $\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$ I needed a complete problem for the class ${NP}^{\#P}$ for a reduction to show the hardness of some other ...
Habri's user avatar
  • 21
0 votes
0 answers
18 views

Any value in a formula that calculates (not look up) the 'order' of a 'Independent Edge Set' OR a 'I.E.S.' given an 'order' on complete graphs?

Any value or interest in a formula that calculates (not look up) the 'integer order' of a given 'Independent Edge Set' OR given an 'Independent Set' calculates the 'integer order' on Complete Graphs? ...
Tim's user avatar
  • 1
3 votes
1 answer
399 views

Intuition on Lupanov's Upper Bound on Circuit Size

The following result, by Lupanov, is a classic in the theory of Boolean function complexity: Theorem: For every boolean function $f$ of $n$ variables: $$C(f) \leq (1 + \alpha_n)\frac{2^n}{n}, \text{ ...
sdsdsd's user avatar
  • 133
-3 votes
1 answer
107 views

Can one do descriptive complexity theory using abstract state machines?

I learned about ASM recently and was interested how it could used for descriptive complexity theory. Such link seems natural to me: you can give construction of algebraic model for formula as an ASM. ...
uhbif19's user avatar
  • 315
2 votes
1 answer
301 views

Deciding finiteness of regular language is NL-complete?

I've been reading the following Habilitation thesis where the author claims (pg. 29): ... First, deciding whether the language of an NFA is finite is in NL ... I'm having trouble seeing why this ...
user avatar
1 vote
0 answers
85 views

Conditional lower bounds for reachability

Are there conditional lower bounds for the deterministic time complexity of directed reachability algorithms? Maybe something linked to the Strong Exponential Time Hypothesis (SETH)? I mean some ...
Nicola Gigante's user avatar
1 vote
0 answers
171 views

Decidability of the complexity of decision problems

This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
A. G's user avatar
  • 111
1 vote
1 answer
125 views

Complexity of analytic functions and integrals

There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this: To which class do analytic elementary functions, including trigonometric ones, ...
roignoirewg's user avatar
5 votes
0 answers
134 views

Do fast satisfiability algorithms imply fast algorithms for parity SAT?

$\oplus$SAT is the problem of deciding if the number of satisfying assignments to a CNF formula is odd (and is the standard complete problem for the class $\oplus$P, or Parity-P). Suppose we have a ...
Michael Lampis's user avatar
7 votes
0 answers
120 views

Why is showing lower bounds for AM communication complexity difficult?

One of the major open problems in communication complexity is to show interesting lower bounds for the Arthur-Merlin (AM) communication complexity of some natural problems (i.e., lower bounds of the ...
Naysh's user avatar
  • 686
0 votes
0 answers
56 views

Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?

The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here: Consider a probabilistic Turing Machine (PTM) $M$, and a language $L \in BPP$: If $x \in L$ (...
hedgehog0's user avatar
1 vote
0 answers
87 views

What complexity class is characterized by having PSPACE verifiers?

Inspired by the 2 definitions (theorems) I am aware of, that are as follows. A language L belongs to QMA if there exists a BQP verifier V. A language L belongs to NP if there exists a P verifier V. ...
Ilk's user avatar
  • 920
1 vote
0 answers
92 views

Generalization of the Hamiltonian path problem on Grid Graphs

Fix a cost to each of these actions: move up, move down, move left, move right. I.e. fix some function $f: \{\text{move up, move down, move left, move right}\} \to \mathbb N$. Define the following ...
TRP's user avatar
  • 31
2 votes
0 answers
61 views

Complexity measures for semi-decidable problems

Is there any sensible complexity measure that makes sense to compare the "hardness" of undecidable semi-decidable problems? Time and space are of course not suitable, because they cannot be ...
Nicola Gigante's user avatar
3 votes
0 answers
110 views

How does NP-completess of decision problems relate to NP-completeness of search problems?

Background Oded Goldreich differentiates in his textbook (Computational Complexity: A Conceptual Perspective) between the "decision" variant of NP problems and "search" variant of ...
Anton Ehrmanntraut's user avatar
15 votes
2 answers
1k views

Law of the Excluded Middle in complexity theory

A recent blog post by Lance Fortnow discusses non-constructive proofs, where "non-constructive" here means that the law of the excluded middle is used in a substantive way. That is, one ...
Timothy Chow's user avatar
  • 7,560
1 vote
0 answers
41 views

Encoding of continuous functions in PPAD

I'm studying the complexity class PPAD (from the seminal 1994 work by Papadimitriou) which contains complete problems such as computing Nash equilibria or finding the fixed point of a Brouwer map. ...
ntrstd11's user avatar
  • 111
1 vote
1 answer
154 views

A contradiction in the realm of quantum digital and analog computation

It is a well known result that the circuit model of Quantum Computing (QC) is equivalent to the adiabatic model. Furthermore, the former is nothing more than a "slightly" more powerful ...
Marion's user avatar
  • 183
9 votes
1 answer
412 views

Is P=NP relative to the halting oracle?

Consider the following variant $\mathscr{H}$ of the halting oracle: given the code $e$ for an ordinary Turing machine and an input $n$ to it, we let $\mathscr{H}(\langle e,n\rangle) = \langle 0,0\...
Gro-Tsen's user avatar
  • 841
3 votes
0 answers
195 views

Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?

It is well-known that $\mathsf{P}\neq\mathsf{SPACE}(n)$, either for $\mathsf{SPACE}=\mathsf{DSPACE}$ or $\mathsf{NSPACE}$, and it is conjectured that both $\mathsf{P}\not\subseteq\mathsf{DSPACE}(n)$ ...
plm's user avatar
  • 131
1 vote
0 answers
106 views

If it is $\#{P}$-hard to compute the sign of the permanent of any matrix, does that imply difficulty in relative approximation of the permanent?

I'm trying to understand the statement in the introduction (pg 1) of this work by Anari et all on approximating the permanent $\text{per}(A)$ of a positive semi-definite matrix $A$. The statement, I'm ...
user135520's user avatar
0 votes
0 answers
60 views

Is there a construction which multiplies and adds spanning trees in Logspace?

I.1 Suppose we have two planar graphs $G_1$ and $G_2$ with spanning tree count $C_1$ and $C_2$ respectively then is there a graph construction in Logspace to get a planar graph from $G_1$ and $G_2$ ...
Turbo's user avatar
  • 13k
4 votes
1 answer
72 views

Complexity of maximum k-edge-colorable subgraph of a bipartite graph

Can the maximum $k$-edge-colorable subgraph of a bipartite graph be found in polynomial time? Equivalently, can the maximum $k$-colorable subgraph of the line graph of a bipartite graph be found in ...
Timothy Chow's user avatar
  • 7,560
7 votes
3 answers
387 views

Structural Complexity Theory References

I'm a PhD student in mathematics (mostly studying algebraic geometry), but I've always been interested in computational complexity theory. As an undergraduate, I completed an independent reading ...
LiminalSpace's user avatar
1 vote
1 answer
122 views

Name and complexity of a stone placement puzzle

Consider the puzzle comprised of $N$ stones. Each stone is given a set of candidate locations. The goal is to put each stone in one of its candidate locations such that no two stones are put in the ...
TRP's user avatar
  • 31
1 vote
0 answers
105 views

Complexity of n-rooks completion

I am motivated by the post, Complexity of n-queens-completion. I am interested in completion problem of non-attacking rooks on a chessboard. Input: Given a chessboard of size $n*n$ with $n-k$ rooks ...
Mohammad Al-Turkistany's user avatar
6 votes
1 answer
357 views

Condition Number dependent algorithms for matrix operations

Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
Thomas Ahle's user avatar
1 vote
0 answers
75 views

Using a certificate in the proof of NP hardness

Say I wanted to determine that the problem of membership in some language $L \subseteq \{0, 1\}^*$ is NP-hard. Say that I have a reduction $r: \{\text{set of quantifier free formulas} \rightarrow \{0,...
Amar Shah's user avatar

1
2
3 4 5
62