# Thread: Mathematician claims breakthrough in complexity theory

1. ## Mathematician claims breakthrough in complexity theory

http://news.sciencemag.org/math/2015...plexity-theory

https://rjlipton.wordpress.com/2015/11/21/a-little-more-on-the-graph-isomorphism-algorithm/

http://www.technologyreview.com/news/543511/claimed-breakthrough-slays-classic-computing-problem-encryption-could-be-next/

https://www.newscientist.com/article/dn28478-complex-problem-made-simple-sends-computer-scientists-wild/

https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem

"Solving an NP-complete problem, the impact on the speed of cryptographic systems and compressors is exponential.
The compressors are based on equality comparison in finite systems that are noted as binary in the archives, and the removal of material classified as equal;
Detecting equalities in an exponentially shorter time, inside in the existing arrangement in the file to be compressed - the compression and decompression speeds can increase exponentially over the best existing algorithms today." 2. ## The Following User Says Thank You to BetaTester For This Useful Post:

avitar (23rd November 2015)

3. The meaning of having polynomial or quasi-polynomial (exp(log(n)^c)) algorithm is greatly overstated - it is very far from P=NP? problem, simple invariants like numbers of vertices of given degree are satisfactory in most cases.
There are rare cases where they are not sufficient (we need better invariants) - when it is very difficult to decide if there exists an automorphism transforming given two vertices.
He says that the problem is with Johnson or Petersen graphs - so the real problem is with probably infinite family of strongly regular graphs ( https://en.wikipedia.org/wiki/Strongly_regular_graph ):
- they are regular (are degrees are equal),
- every two adjacent vertices have λ common neighbours,
- every two non-adjacent vertices have μ common neighbours.
The really nasty examples start with 16 veritces - there exist 2 such graphs:

0111111000000000
1011000111000000
1101000000111000
1110000000000111
1000011100100100
1000101010010010
1000110001001001
0100100011100100
0100010101010010
0100001110001001
0010100100011100
0010010010101010
0010001001110001
0001100100100011
0001010010010101
0001001001001110

and

0111111000000000
1011000111000000
1100100100110000
1100010010001100
1010001000101010
1001001000010101
1000110001000011
0110000001010110
0101000001101001
0100001110000011
0010100010011001
0010010100100101
0001100010100110
0001010100011010
0000101101001100
0000011011110000

such that really sophisticated invariant cannot distinguish their vertices, but there is no isomorphism.

I will have to take a closer look (preprint is not yet available), but the lecture above focuses on what happens after we "individualize" the vertices (e.g. 90-10 division), neglecting its difficulty - while the real problem is there. 4. ## The Following 2 Users Say Thank You to Jarek For This Useful Post:

avitar (23rd November 2015),Cyan (23rd November 2015)

#### Tags for this Thread

discovery math kolmogorov luks algorithm cripto compression #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•