All Questions
1,809 questions
2
votes
0
answers
120
views
integrality of a linear program -- binary equality constaints
Consider the following linear program:
$\left\{
\begin{array}{l}
\underset{x}{max} \;\;c^Tx\\
[I, \;B]x = \mathbf{1}\\
x\geq 0
\end{array}
\right.$
where $c$ is a vector ...
- 127
2
votes
0
answers
123
views
What are natural examples of non-relativizable proofs? [duplicate]
As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles).
Virtually all proofs seem to be relativizable, though.
What are good examples of ...
- 179
2
votes
0
answers
152
views
Reference Request: Properties of the Integer Factorization Polytope
The complexity of Integer Factorization is to my knowledge still an open problem, whereas deciding, whether a given integer is a prime number is known to be in $P$ and a proof is available online here:...
- 13.2k
2
votes
0
answers
250
views
cyclotomic polynomials of given degree
Is there a fast algorithm to generate all cyclotomic polynomials $\Phi_n$ for which the degree of $\Phi_n$ is a fixed constant $d?$ This is obviously related to the "inverse totient" function: compute ...
- 96.4k
2
votes
0
answers
146
views
Odds of projections of a point not on the hyperplane
Let $\mathcal{L}=\{\Bbb x\in\Bbb R^n:x_1+x_2+\dots+x_n=0\}$ be a specific hyperplane.
Let a projection of $c\in\Bbb R^n$ be $p(c)=[p_1,p_2,\dots,p_n]$ where $p_i\neq c_i\implies p_i=0$.
Let $\...
- 13.9k
2
votes
0
answers
179
views
Kolmogorov complexity proof of Lovasz local lemma
Roughly speaking, the Kolmogorov Complexity proof of Lovasz local lemma states that for any $k$-CNF $S$ on $n$ variables and $m$ clauses, where the dependency of every clause is bounded by $2^{k-c}$, ...
- 69
2
votes
0
answers
39
views
In what paper was the shrinkage parameter introduced to the nelder-mead simplex direct search algorithm?
I have read lots of papers referencing a 4th shrinkage parameter when talking about the Nelder Mead Simplex method. However, I cannot see any shrinkage parameter in the flow chart of the original ...
- 21
2
votes
0
answers
163
views
existence of lattice point in polytope
This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
- 501
2
votes
0
answers
63
views
Put positive polynomial in finite intersection of half-spaces
This is a cross-posting of a MSE question (which did not attract any attention there so far).
Denote by $V={\mathcal P}_{n,d}$ the space of polynomials in $n$ variables with degree at most $d$, ...
- 621
2
votes
0
answers
128
views
supersingular curve detector
Suppose I give you a prime $p$ and ask for a non-CM supersingular elliptic curve over $\mathbb{F}_p.$ Can this be done in polynomial time (so, polynomial in $\log p$)?
- 96.4k
2
votes
0
answers
179
views
Randomized alternative to Buchberger's algorithm
Richard Lipton's blog describes a A New Way To Solve Linear Equations by Prasad Raghavendra.
Can the ideas in this algorithm be generalized to systems of polynomial equations to provide a randomized ...
- 529
2
votes
0
answers
230
views
Consistency of a system of linear equations
I have a system of linear equations in form of $AX=b$ where $A_{m\times n}$, $X_{n\times 1}$ and $b_{m\times 1}$. Coefficient matrix $A$ is quite sparse. However, using a practical LP solver like ...
- 221
2
votes
1
answer
137
views
Design constraint systems over the reals
This question is inspired by the discussion at this problem.
Suppose I have a design consisting of a finite point set $U$ of size $|U|=m_{\emptyset}$ and a family of $n$ subsets (sometimes called ...
- 30.1k
2
votes
0
answers
917
views
Guessing game with guess cost
This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...
- 4,952
2
votes
0
answers
120
views
Circuits by Level
Context: googling existing results on Circuit Complexity.
I'm aware there are classes like AC, ACC, TC, NC, etc..
Now, suppose I have a circuit, it has the following additional program:
The circuit ...
- 77
2
votes
0
answers
215
views
Number of breakpoints in parametric maximum flow problems
The parametric maximum flow problem can be formulated as
$$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right),
$$
where all $c_{ij}<0$ (so that ...
- 567
2
votes
0
answers
642
views
Hamiltonian paths in subgraphs of rectangular lattice graphs
Is following decision problem NP-hard / NP-complete:
Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists
Having vertex-induced subgraph of rectangular ...
2
votes
0
answers
123
views
IP[poly] vs AM[poly]
I know the following:
$$IP[k] \subseteq AM[k+2]$$
Now, I also know that
$$ \\#SAT_D \in IP[poly]$$
(As shown on page 159 of Arora/Barak).
In their proof, (and the following proof of $$ TBQF \in ...
- 21
2
votes
0
answers
227
views
Complexity of finding disjoint 2-factors with equal cardinality in cubic graphs?
Finding a connected 2-factor that contains every node in cubic graphs is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding vertex ...
- 2,993
2
votes
0
answers
535
views
Undecidability, Church Turing Thesis, and P/poly
I find the following three facts individually acceptable, but together deeply unsettling:
1) P/poly can decide the unary language $\{ 1^n | M_n(n) \quad \text{halts} \}$ via advice string.
2) Church ...
2
votes
0
answers
143
views
finding set of tree decompositions to cover all pairs of vertices
I first asked this on cstheory.SE but got no reply.
Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How ...
- 2,252
2
votes
0
answers
289
views
Finding globally minimal row subsets of an integer matrix which generate the full row span
Given a $n\times m$ integer matrix $A$, we can consider its row span $span(A)$, that is, the minimal sublattice of $\mathbb{Z}^m$ containing all rows of $A$.
Given a subset of the rows of $A$ it is ...
- 5,654
2
votes
0
answers
313
views
Complexity of a variant of the Mandelbrot set decision problem?
This is a modified version of a question posted on StackExchange TCS.
Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number. Let us define
$M=${$(c,k,r)...
- 2,993
2
votes
0
answers
281
views
Recovering a piecewise affine function
Lets say I have an piecewise affine convex function $f(x_1,x_2)$, on which the following operations are possible:
Computing $f(x_1,x_2)$.
Computing a subgradient to $f$ at $(x_1,x_2)$
Computing all ...
- 567
2
votes
0
answers
2k
views
Quantum computation implications of (P vs NP) [duplicate]
Possible Duplicate:
What impact would P!=NP have on the characterization of BQP?
Before I begin, I had a similar post closed for mentioning the recently released (to be verified) proof that P!=...
- 267
2
votes
0
answers
637
views
What effect would a proof of P≠NP have on the field of complexity theory?
This question is motivated by Scott Aaronson's comment about his bet: "If P≠NP has indeed been proved, my life will change so dramatically that having to pay $200,000 will be the least of it."
http://...
- 89
2
votes
0
answers
5k
views
A system of linear equations with linear constraints
Mathematical problem.
Suppose we have $2n$ indeterminates $x_1,\dots,x_n$ and $y_1,\dots,y_n$ (which are denoted by $q$ with indices and called abundances below) and $m$ subsets $P_1,\dots,P_m$ of $\...
1
vote
2
answers
3k
views
"P vs NP" and "NP vs P/Poly"
It is known
$P \subset P/poly$
$NP \not\subset P/poly \Rightarrow P \neq NP$
However, do we have a proof of:
$P \neq NP \Rightarrow NP \not\subset P/poly$ ?
I.e. is there a world where $P \neq NP$, ...
- 663
1
vote
3
answers
268
views
Where does the game-theoretic characterization of PH come from?
I have read in a few places that $\mathbf{PH}$ can be interpreted in terms of the complexity of determining the winner in two-player games. I would like to know a) the original reference for this ...
- 15.4k
1
vote
2
answers
1k
views
NP-Hard solution question
Hello, i have NP hard problem. Let imagine I have found some polynomial algorithm that find ONLY one of many existing solutions of that problem, but at least one solution (if present in the probem). ...
- 13
1
vote
2
answers
207
views
Complexity of decision problem to decide if permutation group is $k$-transitive
Given a finite permutation group $G$ (a subgroup of the symmetric group on a finite set) in terms of its generators, what is known about the decision problem of deciding if $G$ is $k$-transitive for a ...
- 798
1
vote
3
answers
2k
views
A polynomial-time algorithm for deciding whether a language has a polynomial time algorithm
Let $L$ be a language in $NP$. Then are there any results on whether there exists a polynomial-time algorithm (polynomial in the length of the description of $L$) to decide whether $L \in P$? Are ...
- 601
1
vote
3
answers
1k
views
How can one characterize NP^SAT?
Can you help me understand the class of problems solvable by a nondetermimistic Turing machine with an oracle for SAT running in polynomial time?
- 213
1
vote
2
answers
734
views
What is the most "informative" Yes/No math question you know? [closed]
Imagine that alien civilization contacted you and offered to answer one math question. This should be a Yes/No question (so, you cannot ask for a million-digit binary string encoding the answers to a ...
1
vote
2
answers
751
views
Computational complexity of solution of Pell equation and more
What is computational complexity for computing integral solution of Pell equation .It seems to be in P ,and could any one give an algorithm and reference for proof of it's complexity?
And more,could ...
- 3,094
1
vote
3
answers
1k
views
best deterministic complexity for factoring polynomials over finite field
I would like to know currently what's the best deterministic complexity for factoring polynomials over finite field (without the assumption of GRH)? I have searched on google, there are many source, ...
- 1,109
1
vote
4
answers
3k
views
A subset of all languages which is uncountable?
Maybe I'm being dense here, but can someone give me a subset of the set of all languages which is uncountable and the subset is easy to describe? (Some natural subset -- not like "take the set of all ...
- 2,416
1
vote
2
answers
469
views
'Positive-definite' matrices over finite fields
Let $X$ be an $n \times n$ invertible square matrix over some field $\mathbb{F}$, and let $Y = XX^T$ be the product of the matrix with its transpose.
When $\mathbb{F} = \mathbb{R}$, $Y$ is positive-...
- 12.4k
1
vote
1
answer
160
views
Finding reducible polynomials with restricted factors
Given $f(x),g(x) \in \mathbb{Z}[x]$, two irreducible polynomials, is there a polynomial $h(x) \in \mathbb{Z}[x]$ coprime to $f(x)$ such that $f(x) + g(x)h(x)$ is reducible over $\mathbb{Z}[x]$ with ...
- 13.9k
1
vote
1
answer
219
views
What is the fastest known algorithm for evaluating a homogeneous binary polynomial?
This question was initially posted on math.stackexchange.com, but there is no appropriate answer, hence I have the right to publish it here again.
Let $f(x,y) = \sum_{i = 0}^d f_i x^i y^{d-i}$ be a ...
- 1,833
1
vote
1
answer
366
views
"NP has linear circuits" --> something interesting? [soft, philosophical, open]
Page 121 of Computational Complexity, A Modern Approach states:
6.11 (Open Problem) Suppose make a stronger assumption than $NP \subset P/poly$: every langauge in NP has linear size circuits. Can we ...
1
vote
1
answer
603
views
The smallest altitude amongst the triangles formed by points in the unit circle
Let $S$ be a finite set of points inside the unit circle. Consider all possible triangles formed by three distinct points in $S$, and among all such triangles find the smallest altitude. Denote this ...
- 19
1
vote
3
answers
694
views
unbounded complexity
If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ?
For example what would be the complexity class of the language of "provably halting ...
- 11
1
vote
3
answers
2k
views
How to solve Linear Programming problem with tighter Integer Programming constraints
I want to learn a bit about Linear Programming.
After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally ...
1
vote
1
answer
126
views
a linear programming problem
Recently I have a conjecture on decomposing a linear program into smaller ones. I have tested it in Mathmatica by a lot of examples. However, I cannot prove it. I will appreciate if someone can give ...
- 467
1
vote
1
answer
153
views
Specializing non-trivial primality tests
Primes $p$ are integers with no factors (composite allowed) in $[1,p]$. There is a polynomial time test for them.
Given an interval $[a,b]$ what is the best way to test given integer $q$ has no ...
- 13.9k
1
vote
1
answer
104
views
Finite State Automata Inequivalence?
Given two Nondeterministic Finite State Automaton (A, B).
Q. Do the two recognize different languages?
The Problem is NPComplete if the language has a single alphabet {1}. But PSPACE Complete if the ...
- 215
1
vote
2
answers
1k
views
Algorithm for fast factorization of polynomial over $\mathbb Z$ or over $\mathbb F_p$
I want to fast decompose polynomial over ring of integers (original polynomial has integer coefficients and all of factors have integer coefficients) and also over ring of integers modulo prime number....
- 424
1
vote
2
answers
603
views
Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity
While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of ...
- 2,993
1
vote
2
answers
1k
views
Does the independence of P = NP imply existence of arbitrarily good super-polynomial upper bound for SAT?
Let me first define what "super-polynomial" means.
Definition. We call a function f super-polynomial if for all k, there exists a constant n such that for all x ≥ n, f(x) > xk.
Now please judge ...
- 551