| Presentation | 1998/11/20 Unique Solution Instance Generation for the 3-Satisfiability(3SAT)Problem Mitsuo Motoki, Ryuhei Uehara, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | For the 3-Satisfiability Problem(3SAT), we consider a problem of generating its positive instance(and its solution)randomly. For the problem, it is desirable if an instance generation algorithm produces only(and all)"unique solution instances", i.e., instances with only one solution. In this paper, we consider two simple instance generation algorithms, and estimate the number of clauses required by the algorithms to generate unique solution instances with high probability. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | 3SAT / Positive instance generation algorithm / unique solution instance / theoretical analysis and an experimental result |
| Paper # | COMP98-54 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1998/11/20(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Unique Solution Instance Generation for the 3-Satisfiability(3SAT)Problem |
| Sub Title (in English) | |
| Keyword(1) | 3SAT |
| Keyword(2) | Positive instance generation algorithm |
| Keyword(3) | unique solution instance |
| Keyword(4) | theoretical analysis and an experimental result |
| 1st Author's Name | Mitsuo Motoki |
| 1st Author's Affiliation | Dept.of Mathematical and Computing Sciences Tokyo Institute of Technology() |
| 2nd Author's Name | Ryuhei Uehara |
| 2nd Author's Affiliation | Komazawa University |
| Date | 1998/11/20 |
| Paper # | COMP98-54 |
| Volume (vol) | vol.98 |
| Number (no) | 432 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |