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 answers only
not deleted
user 11142
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.
7
votes
Accepted
NP Hardness proof for permanent of 0-1 matrix
Les Valiant's original paper is beautifully written.
EDIT A simpler proof, with a nice explanation (see Section 3) is given by Ben-Dor and Halevy
- 96.4k
1
vote
Complexity of Max Bisection on cubic planar graphs?
I am pretty sure that the result in
http://rutcor.rutgers.edu/pub/rrr/reports2006/23_2006.pdf
tells us that Max-Bisection is NP-hard on bounded degree planar graphs (however, I think the bound is big …
- 96.4k
1
vote
Pseudorandom Functions / Pseudorandom Permutations
To expand very slightly upon @Steve's words of wisdom, see
http://en.wikipedia.org/wiki/Feistel_cipher
- 96.4k
2
votes
Accepted
testing singularity of integer matrices
This is addressed in Storjohann's paper on computing Smith Normal Form.
- 96.4k
2
votes
Quick tests for Self complementary vertex transitive graphs
A fairly comprehensive survey as of 13 years ago is given in Alastair Farrugia's Master's thesis (see chapter 3, in particular).
- 96.4k
5
votes
Computational complexity of Knot polynomials
Complexity: Knots, Colourings and Counting
By D. J. A. Welsh
Has pretty extensive information.
- 96.4k
15
votes
Computational complexity of computing homotopy groups of spheres
It is shown by D. J. Anick in The computation of rational homotopy groups is #℘-hard. Computers in geometry and topology, Proc. Conf., Chicago/Ill. 1986, Lect. Notes Pure Appl. Math. 114, 1–56, 1989. …
- 96.4k
2
votes
How long does it take to compute a class number?
J. Buchmann and M. Pohst in a 1989 paper show that the class group can be computed in time of order $D^{1+\epsilon},$ where $D$ is the discriminant.
- 96.4k
6
votes
Are there any efficient (polynomial time) algorithms for finding if a multivariate quadratic...
I might be misunderstanding the question, but if the equation is homogeneous, then zero is a solution, if the homogeneous (degree 2) part is an indefinite quadratic form, then the equation has a solut …
- 96.4k
4
votes
Examples of ubiquitous objects that are hard to find?
A random pair of elements of $\mathop{SL}(n, \mathbb{Z})$ (where random is defined by taking a generating set, and picking two random long words) almost certainly (meaning, with probability approachin …
2
votes
Is unconstrained integer convex optimization problem NP-hard?
Yes, since the shortest vector in lattice problem is NP-hard, see http://en.wikipedia.org/wiki/Lattice_problem
- 96.4k
4
votes
Maximizing positive definite quadratic using the eigendecompoisition
The reference where all is revealed is Bodlaender, Gritzman, Klee, Van Leeuwen
- 96.4k
5
votes
Computational complexity of finding the smallest number with n factors
The number of divisors of $n = \prod_{i=1}^k p_i^{\alpha_i}$ is
$g(n)=\prod_{i=1}^k (1+\alpha_i)$ (your function differs from this by $2.$)
So, once you have $g(n),$ you find the minimum over all fac …
- 96.4k
2
votes
Complexity of 2D-Minkowski sum of non-convex polygons
See Eli Fogel's slides. and be enlightened.
- 96.4k
7
votes
Can all convex optimization problems be solved in polynomial time using interior-point algor...
You should check out Boyd-Vanderberghe's convex optimization, available for free on Boyd's web page at Stanford. This has a discussion of the "easy" classes of convex optimization problems (google "se …
- 96.4k