Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with computational-complexity
Search options questions only
not deleted
user 10035
This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.
1
vote
0
answers
104
views
Simultaneous elimination of variables in multiple polynomials
I have a system of $n=O(1)$ non-homogeneous polynomials of total degree $d=O(1)$ $p_1,\dots,p_r\in \mathbb Z[x_1,\dots,x_n]$. I would like to eliminate $n-1$ variables simultaneously from the $n$ poly …
- 13.9k
1
vote
0
answers
88
views
Proof for non-existence of short integer program for squares
We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question.
Is there a way to show within an …
- 13.9k
2
votes
0
answers
90
views
Why cannot we adapt Barvinok type counting techniques to general convex integer programs?
Decision problems in Integer Linear Programming have Lenstra type algorithms (https://www.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf) have been generalized to convex integer program tech …
- 13.9k
3
votes
1
answer
328
views
Nonexistence of short integer program sequence which generates squares
Is there a way to show within an integer program with constant number of variables and constraints of length $poly(\log B)$ (say length $\leq10^{1000000}\log B$), it is not possible for a variable to …
- 13.9k
3
votes
1
answer
272
views
On shortest vector problem
Assume we have an oracle which gives the length of the shortest vector in a lattice. Given this oracle can we find the shortest vector in polynomial time?
- 13.9k
1
vote
0
answers
34
views
Does $2$ variable linear Diophantine equation in $NC$ imply $2$ dimensional shortest vector ...
Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$
$$ax+by=c.$$
Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ …
- 13.9k
1
vote
0
answers
101
views
On determinant and permanent of certain homotopy defined simple matrices
Let $A_1,A_2,B_1,B_2$ be four $n\times n$ $0/1$ square matrices where $$\det(A_1)=\det(A_2)=per(A_1)=per(A_2)=1$$
$$\det(B_1)=\det(B_2)=per(B_1)=per(B_2)=0$$
hold ($per$ refers to permanent).
I. What …
- 13.9k
1
vote
0
answers
161
views
On an optimization question
Suppose we have a square matrix $M=(1-z)A+zB$ where $A,B$ have integer entries from $\{0,1\}$ with $\det(A)+\det(B)=1$ and $\det(A),\det(B),per(A),per(B)\in\{0,1\}$ and we want to find $z\in[0,1]$ tha …
- 13.9k
2
votes
0
answers
214
views
Modular inverse computation - avoiding Euclidean algorithm
Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know t …
- 13.9k
0
votes
0
answers
121
views
Will an integer program to deterministically factor integers help derandomize $\mathbb F_q[x...
There are many analogies between the objects $\mathbb F_q[x]$ and $\mathbb Z$.
Supposing there is a fixed (say $10^9$) dimension linear integer program (describable without any objective function) in …
- 13.9k
2
votes
1
answer
476
views
Modular square roots problem which is $NP$ hard
It is well known extracting modular square roots modulo a composite number factors the modulus.
On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $NP$ …
- 13.9k
1
vote
0
answers
69
views
Is this factorization problem in EXP?
Factorization is not known to have a polynomial time algorithm. Traditionally the input length is number of bits in representation of the integer to be factored.
However now consider integers of form …
- 13.9k
2
votes
0
answers
197
views
On GCD and lattice reduction
$LLL$ algorithm is vectorized version of Euclidean algorithm for $GCD$.
Even the $m=2$ case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector.
If $GCD$ is in $NC$ and in …
- 13.9k
4
votes
0
answers
104
views
Questions in number theory related to $NC$ and $P$-completeness
Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$.
Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$.
Euclidean algorithm solves both.
My question is if either 1 or 2 is i …
- 13.9k
2
votes
1
answer
171
views
On roots of irreducible quadratics modulo composites
Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$
Is this problem equivalent to any hardness results?
- 13.9k