Results 1 to 2 of 2

Thread: Mathematician claims breakthrough in complexity theory

  1. #1
    Member BetaTester's Avatar
    Join Date
    Dec 2010
    Location
    Brazil
    Posts
    43
    Thanks
    0
    Thanked 3 Times in 3 Posts

    Lightbulb 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. #2
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    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.
    Last edited by Jarek; 23rd November 2015 at 09:56.

  4. The Following 2 Users Say Thank You to Jarek For This Useful Post:

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

Similar Threads

  1. Replies: 25
    Last Post: 4th January 2017, 17:02
  2. Replies: 11
    Last Post: 15th November 2015, 12:10
  3. 100% Lossless Compression Theory - Please Join Me
    By SmallestFilePoss in forum Data Compression
    Replies: 16
    Last Post: 24th September 2013, 22:33
  4. Paq mixer theory
    By Shelwien in forum Data Compression
    Replies: 0
    Last Post: 22nd November 2009, 02:32

Tags for this Thread

Posting Permissions

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