All Questions
12,695
questions
13
votes
1
answer
898
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 ...
- 7,465
1
vote
0
answers
39
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. ...
- 111
1
vote
1
answer
140
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 ...
- 183
0
votes
0
answers
63
views
What is the meaning of the additive epsilon term in the definition of a time constructible function?
There is a well-known theorem that states that a function $f$ is time constructible if and only if $f$ can be computed in time $O(f)$. But this theorem comes with some conditions: $f$ must be a ...
-1
votes
1
answer
74
views
What is the type of the lambda term $\lambda a.a(\lambda yt.t)(ya)$?
I was given an exercise that asked me to assign a simple type to the lambda term:
$$
\lambda a.a(\lambda yt.t)(ya)
$$
but I couldn't find one, furthermore, the lambda term seems untypable to me ...
9
votes
1
answer
328
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\...
- 619
3
votes
0
answers
163
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)$ ...
- 131
7
votes
0
answers
164
views
Project management
What book or MOOC would you recommend on work organisation / management of academic research projects? (Does not have to be academic project management specifically, but as close as possible)
7
votes
1
answer
293
views
Is there a well-defined notion of an “R/poly” complexity class?
This would be the complexity class of all problems that are decidable in finite time with a polynomial length advice string that can be arbitrarily hard to compute. But potentially undecidable without ...
- 331
6
votes
0
answers
274
views
Techniques for solving huge linear programs
During the solution of some computational problem, we have arrived at a linear program of the following form:
\begin{align*}
\text{maximize} ~~ c x
\\
\text{subject to} ~~ A x \leq b, x \geq 0
\...
- 2,078
7
votes
1
answer
279
views
Is is true that every monad transformer is equivalent to its underlying/base monad?
Question originally asked in proofassistants.stackexchange
Just like the title says, is it true (in some sensible model)? And if so, how to prove it? Something tells me it should be true and higher-...
- 209
4
votes
1
answer
98
views
Power of non-implicationally-complete Frege systems and Boolean equational calculus
We know that Frege systems are required to be implicationally complete -- namely, if a set of formulas $B_1,B_2,\cdots,B_t$ imply formula $C$, then this implication can be proven in the system. I'm ...
- 177
1
vote
0
answers
38
views
Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights
I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
- 111
4
votes
1
answer
86
views
Methods for Determining the minimal Width of Resolution Refutations for CNF Formulas
Recall that the width of a resolution refutation $R$ of a CNF formula $F$ is the maximal number of literals in any clause occurring in $R$. I am intersting in finding the minimal width of some certain ...
- 315
0
votes
0
answers
50
views
Product types: algebraic structure for modeling product types with commutative and associative product operation
Is there a known algebraic structure over set of Types (however they are defined) which is equipped with:
commutative and associative product operation for building product types from simpler types, ...
2
votes
0
answers
51
views
Formal semantics of a simple object oriented language without inheritance but with self-referential objects
Would you please point me to some papers or textbooks that describe rigorously a formal semantics/computational model of a simple object-oriented language? The language needs not accommodate ...
- 354
1
vote
0
answers
99
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 ...
- 111
1
vote
0
answers
51
views
Is this proof for completeness of regular model checking correct?
In "Calculational Design of A Regular Model Checker by Abstract Interpretation" by Patrick Cousot (link), on page 15 it can be seen that to prove the completeness of regular model checking (...
- 13
12
votes
1
answer
233
views
Complexity of 1-or-3-in-3-SAT (odd-3-SAT)
Consider a 3-CNF formula $\Phi$, i.e., a conjunction of clauses of 3 literals. I call odd-SAT (or 1-or-3-in-3-SAT) the problem of checking whether there is an assignment of the variables such that ...
- 8,916
4
votes
1
answer
52
views
References on second-order quantifier elimination and related topics
I was wondering whether something like elimination of second-order quantifiers exist, and indeed it seems it does. I've found there's a workshop on this topic, and the webpage describes exactly what I ...
- 1,588
5
votes
1
answer
153
views
Are there complexity teaching resources that do not treat NP-hardness gadgets as Voodoo magic?
I am teaching a mini-complexity course to high achieving high-school students from my country this fall, and they have all expressed strong interest in learning more about what $P, NP$, reductions, ...
- 1,088
2
votes
2
answers
114
views
Linear Programming Sensitivity to Matrix
Consider a linear program in the following standard form:
\begin{align*}
&\max c^T x &\\
&\mbox{subject to:}\\
&A x \preceq b\\
&x \succeq 0
\end{align*}
Its dual is
\begin{align*}...
- 575
7
votes
1
answer
155
views
Complexity of the inevitability problem over monoids
I am interested in the complexity of following problem:
Inevitability problem in monoids
Input: two regular languages $K$, $L$ specified by finite monoids $M_K$ and $M_L$ (+ morphisms and accepting ...
- 143
7
votes
1
answer
334
views
Converting 2-ambiguous NFA to unambiguous NFA
This must be known, but somehow I can't locate a reference about this. Let $A$ be a nondeterministic finite automaton (NFA) over words of an alphabet $\Sigma$. I say that $A$ is unambigous if, for ...
- 8,916
0
votes
0
answers
56
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$ ...
- 12.8k
0
votes
0
answers
32
views
Hardness of finding minimal subsets that will change the maximum of a univariate polynomial
Given a univariate polynomial of the form $p(x) = \prod_{0 \leq i \leq N}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$ (we are given all ...
- 11
4
votes
0
answers
132
views
Which variant of the ellipsoid method was used for the Santa Claus problem?
As one of the steps in the article The Santa Claus problem (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the dual):
\begin{align*}
&\...
- 91
-3
votes
1
answer
96
views
Algebra in complexity theory
Recently an idea came to my mind. Suppose $V$ is vector space and $\dim V = n$. Then, since $V \simeq \mathbb{R}^n$, any conjunction of $n$ boolean formulas $\phi_1, \ldots, \phi_n$ about vectors from ...
- 1
1
vote
1
answer
85
views
Approximating the utilitarian welfare minus a constant
Assume we have $n$ agents and $m$ indivisible goods that need to be allocated among the agents such that their sum of utilities is maximized.
Denote the set of allocations by $\mathcal{A}$ and the ...
- 91
1
vote
0
answers
75
views
Hardness of maximization of a univariate polynomial (as a function of its degree)
Given a univariate polynomial of the form $p(x) = \prod_{i}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$.
What is the complexity of ...
- 11
3
votes
0
answers
46
views
Approximate decomposition of a many-to-one assignment
Suppose we have $n$ items and $n$ agents and we want to assign one item to each agent. We have a probability matrix $P$ such that $p_{i,j}$ is the probability that agent $i$ gets item $j$. If $\sum_j ...
- 2,078
0
votes
0
answers
67
views
Sizes of tableau in PH
When one proves that SAT is NP-complete, one uses a tableau of size $n^k \times n^k$. Similarly, when one proves that TQBF is PSPACE-complete one uses a tableau of size $2^{n^k} \times n^k$. Thus, I'm ...
- 921
2
votes
0
answers
43
views
Submodulare welfare maximization: is an additive approximation algorithm known?
Sudmodular welfare maximization is the problem of allocating items among agents with different valuations, represented by submodular set functions, such that the sum of agents' values is as large as ...
- 2,078
1
vote
0
answers
56
views
Constructing lossless conductors using zigzag product - a doubt
Reference - this survey: https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf
I am reading the section on constructing lossless conductors using a bipartite variant of zigzag product (section 10,...
- 91
-2
votes
1
answer
88
views
Polynomial vs. Exponential Time Complexity [closed]
Does $2^{log_2{n}}$ grow faster than a polynomial? I know that $2^{log_2{n}}$ can be simplified as $n$ but can it be considered as an exponential?
0
votes
0
answers
64
views
Enumerating all set covers with sets of size at most two
I am working on enumerating all the set covers (need not be minimal). A branching algorithm runs in $O^*(1.2353^{|U|+|S|})$ time that branches on all the sets of size at least three. As the branching ...
0
votes
0
answers
83
views
5-color graph and minor
We have a 5-color graph G without 5-clique. The question is: is there a minor H of G that is a 5-clique? Here the minor definition.
With "5-color graph G" I mean $\chi (G)=5$.
4
votes
1
answer
63
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 ...
- 7,465
1
vote
0
answers
134
views
How "Algebrization" is "A New Barrier in Complexity Theory"?
Being an enthusiast in computational complexity theory, I recently came across with this wonderful work Algebrization: A New Barrier in Complexity Theory.
My question is about Theorem 5.3 in it (pp. ...
- 19
0
votes
0
answers
59
views
Prove that Vertex Cover is NP-Complete by reducing MaxCut to Vertex Cover
This is not the most straight forward reduction available on the internet since most people start from the fact that vertex cover is NP-complete and reduce a given vertex cover instance to MaxCut ...
- 11
6
votes
3
answers
335
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 ...
- 113
2
votes
0
answers
154
views
Semi-Thue systems and deterministic computation
I would like to use semi-Thue systems (a.k.a. string rewriting systems) to study complexity theory formally. Note that "semi-" in the name means "unidirectional [Thue system]".
...
1
vote
1
answer
103
views
Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths
I am working on a problem involving partitioning a directed acyclic graph into distinct multiple paths, each with a maximum length constraint. The goal is to minimize the number of paths (this should ...
- 11
2
votes
1
answer
52
views
Database repository containing queries
For my research, I need to find real database queries (just queries, I do not need the data). However, the unique public "real" queries I know are those appearing in the TPC benchmarks.
Does ...
- 131
1
vote
0
answers
74
views
Testing positivity of a function by an IP system?
We are given a polynomial function $f:\{0,1\}^n\to\mathbb{R}$ with $\text{deg}(f)\leq d$ ($d$ is constant), and $\epsilon>0$; $f$ here is presented by its coefficients (the degree is constant, so ...
- 111
1
vote
1
answer
112
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 ...
- 31
1
vote
0
answers
33
views
Application LCL definition to vertex coloration
I'm reading the article "What can be computed locally?" by Naor & Stockmeyer and I struggle to understand the definition of an LCL they gave. Here is an extract: (page 2)
An Locally ...
- 111
1
vote
0
answers
35
views
Overlap operator for simple ( regex-like ) Patterns
( Introduction )
Some Notation
lower case letters, $a, b, c$ will be used to denote single symbols
Upper case letters, $P, Q, R$ will be used to denote string of symbols
$a\!:\!S$ means a string ...
- 11
1
vote
0
answers
84
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 ...
- 20.8k
7
votes
0
answers
79
views
How is FNP defined? Or, is FNP closed under relaxation?
I hope this isn't a dumb question, but I've been driving myself nuts regarding the following.
The definition of $\mathsf{FNP}$ that I've found in many places is the following:
A relation $R(x,y)$ is ...
- 1,204