Newest Questions
13,478 questions
3
votes
0
answers
45
views
Reasons to believe $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$
Much has been said about $\mathsf{P} =^? \mathsf{NP}$. Many polls have been done, and now I think almost every expert believes in $\neq$: https://en.wikipedia.org/wiki/P_versus_NP_problem#Context
...
- 131
4
votes
1
answer
379
views
Semantic proof of lambda calculus consistency?
The question Scott on the consistency of the lambda calculus on MO discusses the consistency of the lambda-calculus (which I take to mean the confluence property, as formalized in the Church-Rosser ...
- 503
2
votes
0
answers
113
views
Does resolution admit polynomial-size proofs for sorting encoded as CNF?
I am studying the connection between SAT encodings and proof complexity.
Suppose we take a sorting problem (for example, verifying that the output is a sorted permutation of the input) and encode it ...
- 239
1
vote
0
answers
43
views
pullbacks and cartesian arrows
$B$ is a category with pullbacks. For a fibration $P \colon E \to B$, the following are true
a commutative square of cartesian arrows in $E$ over a pullback in $B$ is always a pullback in $E$
A ...
- 161
6
votes
1
answer
288
views
Complexity of CNF-SAT parameterized by the number of clauses
Consider the CNF-SAT problem: we are given as input a Boolean formula $\Phi$ in conjunctive normal form (CNF), and we must decide whether it is satisfiable. This is a well-known NP-complete problem. ...
- 10.9k
-2
votes
0
answers
98
views
If the Upper Bound of the Factoring Period is N, Is Shor's Algorithm Actually Exponential?
On Math StackExchange, I asked a question about the upper bound of the period $r$ for factoring. I believe the upper bound is (essentially) $N$, the $n$-bit number to be factored.
If true, this means ...
1
vote
1
answer
138
views
Simplest example of a "natural" complete problem for a TFNP class
There are now many examples of "natural" (no mention of circuits) problems which have been proven to be complete for classical TFNP classes---these include Consensus Halving for PPA and ...
- 330
5
votes
0
answers
205
views
Hidden constant in complexity of the AKS primality test
In the AKS paper, the authors based on the Lemma
There exist constants $c > 0$ and $n_0$ such that, for all $x\ge n_0$: $$\bigl|\{q \mid \text{$q$ is prime, $q\le x$ and $P(q − 1) > q^{2/3}$}\}\...
- 151
6
votes
0
answers
195
views
Does $\mathsf{FP} \subseteq \mathsf{FNP}$ really hold?
The following definitions are from Elaine Rich's Automata, Computability and Complexity.
The Class FP: A binary relation $Q$ is in $\mathsf{FP}$ iff there is a deterministic polynomial time algorithm ...
- 161
1
vote
0
answers
45
views
Budgeted maximum coverage with integer weights
In the budgeted maximum coverage problem, we have a collection of sets with weights. The goal is to find a collection of sets whose total weight does not exceed some given budget L. One can also ...
6
votes
0
answers
116
views
About hardness result for ILP with fixed number of variable
It is known that ILP with a fixed number of variables is in $\mathsf{P}$[Les83]. (For convenience, the decision version of the problem is given in the post.)
I have the following two questions ...
- 426
2
votes
0
answers
48
views
Packing induced $P_3$s and their complements
I'm interested in vertex-disjoint packing of induced $P_3$s (paths on three vertices) and their complements. Is this problem NP-hard?
Observation: A graph is $\{P_3, \overline{P_3}\}$-free if and only ...
- 2,619
2
votes
0
answers
78
views
Fast computation of volume of overlapping unit balls
Suppose I have $n$ (partially overlapping) unit balls in Euclidean space $\mathbb{R}^d$. What is a fast algorithm for computing their volume?
Motivation: The Kneser–Poulsen conjecture states that if ...
- 7,826
11
votes
1
answer
348
views
Extending Fliess theorem to weighted automata over commutative semirings
I was working on a problem that turned out to be unexpectedly connected to weighted automata. Along the way, I encountered an independent but rather interesting question that I thought would be worth ...
- 251
2
votes
0
answers
61
views
Cache-Oblivious large integer multiplication
Given two $n$-bit integers $a$ and $b$ how many memory transfers are needed to compute $ab$?
Since $ab$ can be computed in $O(n \log n)$ time, this is an upper bound on the number of memory transfers. ...
- 161