Journal article
Dissection: A New Paradigm for Solving Bicomposite Search Problems
Communications of the ACM, Vol.57(10), pp.98-105
Oct/2014
Abstract
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.
Details
- Title
- Dissection; A New Paradigm for Solving Bicomposite Search Problems
- Creators
- Itai Dinur (null) - 972WIS_INST___83Orr Dunkelman (null) - 972WIS_INST___83Nathan Keller (null) - 972WIS_INST___84Adi Shamir (null) - 972WIS_INST___83
- Resource Type
- Journal article
- Publication Details
- Communications of the ACM, Vol.57(10), pp.98-105; Oct/2014
- Number of pages
- 8
- Language
- English
- DOI
- https://doi.org/10.1145/2661434
- Grant note
- Israel Science Foundation [827/12]; German-Israeli Foundation for Scientific Research and Development [2282-2222.6/2011]; Alon FellowshipThe second author (O.D.) was supported in part by the Israel Science Foundation through grant No. 827/12 and in part by the German-Israeli Foundation for Scientific Research and Development through grant No. 2282-2222.6/2011. The third author (N.K.) was supported by the Alon Fellowship._ALMAME_DELIMITER_
- Record Identifier
- 993262060303596
Metrics
10 Record Views