Abstract | ||
---|---|---|
It is well-known that succinct encodings of computational problems – using circuits or formulas to encode large instances – generally result in an exponential complexity blow-up compared to their original complexity. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1016/j.ic.2016.06.009 | Information and Computation |
Keywords | Field | DocType |
Complexity,Succinct,Graphisomorphism,CNF,DNF | Complexity class,ENCODE,Discrete mathematics,Graph,Computational problem,Combinatorics,Exponential function,Succinct data structure,PSPACE,Mathematics,Graph isomorphism problem | Journal |
Volume | ISSN | Citations |
253 | 0890-5401 | 1 |
PageRank | References | Authors |
0.37 | 6 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bireswar Das | 1 | 66 | 10.61 |
Patrick Scharpfenecker | 2 | 8 | 2.22 |
Jacobo Torán | 3 | 564 | 49.26 |