Dissection: A New Paradigm for Solving Bicomposite Search Problems.
Combinatorial search problems are usually described by a collection of possible states, a list of possible actions which map each current state into some next state, and a pair of initial and final states. The algorithmic problem is to find a sequence of actions which maps the given initial state in...
| Publicado en: | Communications of the ACM Vol. 57; no. 10; pp. 98 - 106 |
|---|---|
| Autores principales: | , , , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Oct2014
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=98607836&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 98607836 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Oct2014 vid: 57 iid: 10 pid: 68 pub: Association for Computing Machinery artinfo: ui: 98607836 10.1145/2661434 ppf: 98 ppct: 8 formats: tig: atl: Dissection: A New Paradigm for Solving Bicomposite Search Problems. aug: au: Dinur, Itai Dunkelman, Orr Keller, Nathan Shamir, Adi affil: Computer Science Department, The Weizmann Institute, Rehovot, Israel Computer Science Department, University of Haifa, Israel Department of Mathematics, Bar-Ilan University, Israel su: Combinatorics Search algorithms Spacetime Rubik's Cube Cryptography Boolean functions Computational complexity Mathematical variables sug: subj: Combinatorics Search algorithms Spacetime Rubik's Cube Cryptography Boolean functions Computational complexity Mathematical variables ab: Combinatorial search problems are usually described by a collection of possible states, a list of possible actions which map each current state into some next state, and a pair of initial and final states. The algorithmic problem is to find a sequence of actions which maps the given initial state into the desired final state. In this paper, we introduce the new notion of bicomposite search problems, and show that they can be solved with improved combinations of time and space complexities by using a new algorithmic paradigm called dissection. To demonstrate the broad applicability of our new paradigm, we show how to use it in order to untangle Rubik’s cube and to solve a typical NP-complete partition problem with algorithms which are better than any previously described algorithm for these problems. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2014 holdings: @attributes: islocal: N |
|---|