## New answers tagged computational-complexity

2
votes

### Why do almost all points in the unit interval have Kolmogorov complexity 1?

By the Point-to-Set principle (Lutz & Lutz 2018), for any $\varepsilon$ the set of real numbers with Kolmogorov complexity at most $\varepsilon$ has Hausdorff dimension $\varepsilon$. As $\mathbb{...

- 3,629

20
votes

Accepted

### Why do almost all points in the unit interval have Kolmogorov complexity 1?

I'm not an expert on Kolmogorov complexity, but this does seem like a counting argument: for any fixed $\epsilon > 0$, there are only $\sum_{i = 1}^{(1-\epsilon)n} 2^i < 2^{(1-\epsilon)n+1}$ ...

- 1,519

1
vote

Accepted

### How to find the maximum of a sum of squares of sums?

You can solve the problem via binary quadratic programming as follows. Let binary decision variable $x_{id}$ indicate whether row $i$ is rotated $d$ places. The problem is to maximize
$$\sum_{j=0}^{...

- 4,088

4
votes

### Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?

Just adding some brief clarification to Carlo's answer.
The randomness in the randomized constructions is used solely to randomly produce a lattice that satisfies certain properties.
In particular, ...

- 1,033

9
votes

Accepted

### Is it still not known whether the construction of shortest nonzero vector of a lattice w.r.t. $l^2$-norm is NP-hard?

The NP-hardness of the shortest vector problem in $L_2$ norm is discussed in this 2015 lecture by Vinod Vaikuntanathan. An algorithm for this problem would give a randomised algorithm for any problem ...

- 155k

1
vote

Accepted

### Computational complexity and commuting functions, examples and conjectures

This is not a proper answer. I will give a construction of a pair of functions $f,g$ assuming the access to some cryptographic function $e$ that probably should form a counterexample for Proposition ...

- 4,468

Top 50 recent answers are included

#### Related Tags

computational-complexity × 1226algorithms × 218

co.combinatorics × 217

graph-theory × 188

nt.number-theory × 137

lo.logic × 111

computer-science × 111

computability-theory × 96

reference-request × 87

np × 72

computational-number-theory × 56

linear-algebra × 51

gr.group-theory × 42

combinatorial-optimization × 36

polynomials × 32

ag.algebraic-geometry × 31

matrices × 30

oc.optimization-and-control × 30

pr.probability × 26

prime-numbers × 24

discrete-geometry × 24

graph-colorings × 23

cryptography × 22

approximation-algorithms × 22

computational-geometry × 20