Dichotomy theorem for the generalized unique satisfiability problem
Identifieur interne : 000C86 ( Istex/Corpus ); précédent : 000C85; suivant : 000C87Dichotomy theorem for the generalized unique satisfiability problem
Auteurs : Laurent JubanSource :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: The unique satisfiability problem, that asks whether there exists a unique solution to a given propositional formula, was extensively studied in the recent years. This paper presents a dichotomy theorem for the unique satisfiability problem, partitioning the instances of the problem between the polynomial-time solvable and coNP-hard cases. We notice that the additional knowledge of a model makes this problem coNP-complete.We compare the polynomial cases of unique satisfiability to the polynomial cases of the usual satisfiability problem and show that they are incomparable. This difference between the polynomial cases is partially due to the necessity to apply parsimonious reductions among the unique satisfiability problems to preserve the number of solutions. In particular, we notice that the unique not-all-equal satisfiability problem, where we ask whether there is a unique model such that each clause has at least one true literal and one false literal, is solvable in polynomial time.
Url:
DOI: 10.1007/3-540-48321-7_27
Links to Exploration step
ISTEX:36A26C2FA4AFB12688D7EC9C12827C7CB7C8AD4BLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Dichotomy theorem for the generalized unique satisfiability problem</title><author><name sortKey="Juban, Laurent" sort="Juban, Laurent" uniqKey="Juban L" first="Laurent" last="Juban">Laurent Juban</name><affiliation><mods:affiliation>LORIA (Universitè Henri Poincarè Nancy 1), BP 239, 54506, Vandœuvre-lèes-Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: juban@loria.fr</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:36A26C2FA4AFB12688D7EC9C12827C7CB7C8AD4B</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1007/3-540-48321-7_27</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-2D3SH7CB-V/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000C86</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000C86</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Dichotomy theorem for the generalized unique satisfiability problem</title><author><name sortKey="Juban, Laurent" sort="Juban, Laurent" uniqKey="Juban L" first="Laurent" last="Juban">Laurent Juban</name><affiliation><mods:affiliation>LORIA (Universitè Henri Poincarè Nancy 1), BP 239, 54506, Vandœuvre-lèes-Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: juban@loria.fr</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The unique satisfiability problem, that asks whether there exists a unique solution to a given propositional formula, was extensively studied in the recent years. This paper presents a dichotomy theorem for the unique satisfiability problem, partitioning the instances of the problem between the polynomial-time solvable and coNP-hard cases. We notice that the additional knowledge of a model makes this problem coNP-complete.We compare the polynomial cases of unique satisfiability to the polynomial cases of the usual satisfiability problem and show that they are incomparable. This difference between the polynomial cases is partially due to the necessity to apply parsimonious reductions among the unique satisfiability problems to preserve the number of solutions. In particular, we notice that the unique not-all-equal satisfiability problem, where we ask whether there is a unique model such that each clause has at least one true literal and one false literal, is solvable in polynomial time.</div></front></TEI><istex><corpusName>springer-ebooks</corpusName><author><json:item><name>Laurent Juban</name><affiliations><json:string>LORIA (Universitè Henri Poincarè Nancy 1), BP 239, 54506, Vandœuvre-lèes-Nancy, France</json:string><json:string>E-mail: juban@loria.fr</json:string></affiliations></json:item></author><arkIstex>ark:/67375/HCB-2D3SH7CB-V</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: The unique satisfiability problem, that asks whether there exists a unique solution to a given propositional formula, was extensively studied in the recent years. This paper presents a dichotomy theorem for the unique satisfiability problem, partitioning the instances of the problem between the polynomial-time solvable and coNP-hard cases. We notice that the additional knowledge of a model makes this problem coNP-complete.We compare the polynomial cases of unique satisfiability to the polynomial cases of the usual satisfiability problem and show that they are incomparable. This difference between the polynomial cases is partially due to the necessity to apply parsimonious reductions among the unique satisfiability problems to preserve the number of solutions. In particular, we notice that the unique not-all-equal satisfiability problem, where we ask whether there is a unique model such that each clause has at least one true literal and one false literal, is solvable in polynomial time.</abstract><qualityIndicators><score>8.788</score><pdfWordCount>5496</pdfWordCount><pdfCharCount>26572</pdfCharCount><pdfVersion>1.3</pdfVersion><pdfPageCount>11</pdfPageCount><pdfPageSize>431.3 x 666 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>149</abstractWordCount><abstractCharCount>1010</abstractCharCount><keywordCount>0</keywordCount></qualityIndicators><title>Dichotomy theorem for the generalized unique satisfiability problem</title><chapterId><json:string>27</json:string><json:string>Chap27</json:string></chapterId><genre><json:string>conference</json:string></genre><serie><title>Lecture Notes in Computer Science</title><language><json:string>unknown</json:string></language><copyrightDate>1999</copyrightDate><issn><json:string>0302-9743</json:string></issn><editor><json:item><name>Gerhard Goos</name><affiliations><json:string>Karlsruhe University, Germany</json:string></affiliations></json:item><json:item><name>Juris Hartmanis</name><affiliations><json:string>Cornell University, NY, USA</json:string></affiliations></json:item><json:item><name>Jan van Leeuwen</name><affiliations><json:string>Utrecht University, The Netherlands</json:string></affiliations></json:item></editor></serie><host><title>Fundamentals of Computation Theory</title><language><json:string>unknown</json:string></language><copyrightDate>1999</copyrightDate><doi><json:string>10.1007/3-540-48321-7</json:string></doi><issn><json:string>0302-9743</json:string></issn><eisbn><json:string>978-3-540-48321-2</json:string></eisbn><bookId><json:string>3-540-48321-7</json:string></bookId><isbn><json:string>978-3-540-66412-3</json:string></isbn><volume>1684</volume><pages><first>327</first><last>337</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Gabriel Ciobanu</name><affiliations><json:string>Faculty of Computer Science, “A.I.Cuza” University, 6600, Iaşi, Romania</json:string><json:string>E-mail: gabriel@info.uaic.ro</json:string></affiliations></json:item><json:item><name>Gheorghe Păun</name><affiliations><json:string>Institute of Mathematics of the Romanian Academy, P.O. Box 1-764, 70700, Bucharest, Romania</json:string><json:string>E-mail: gpaun@imar.ro</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Theory of Computation</value></json:item><json:item><value>Discrete Mathematics in Computer Science</value></json:item><json:item><value>Data Structures</value></json:item></subject></host><ark><json:string>ark:/67375/HCB-2D3SH7CB-V</json:string></ark><publicationDate>1999</publicationDate><copyrightDate>1999</copyrightDate><doi><json:string>10.1007/3-540-48321-7_27</json:string></doi><id>36A26C2FA4AFB12688D7EC9C12827C7CB7C8AD4B</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-2D3SH7CB-V/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-2D3SH7CB-V/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/HCB-2D3SH7CB-V/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Dichotomy theorem for the generalized unique satisfiability problem</title></titleStmt><publicationStmt><authority>ISTEX</authority><availability><licence>Springer-Verlag Berlin Heidelberg</licence></availability><date when="1999">1999</date></publicationStmt><notesStmt><note type="conference" source="proceedings" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</note><note type="publication-type" subtype="book-series" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</note></notesStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Dichotomy theorem for the generalized unique satisfiability problem</title><author><persName><forename type="first">Laurent</forename><surname>Juban</surname></persName><email>juban@loria.fr</email><affiliation><orgName type="institution">LORIA (Universitè Henri Poincarè Nancy 1)</orgName><address><street>BP 239</street><postCode>54506</postCode><settlement>Vandœuvre-lèes-Nancy</settlement><country key="FR">FRANCE</country></address></affiliation></author><idno type="istex">36A26C2FA4AFB12688D7EC9C12827C7CB7C8AD4B</idno><idno type="ark">ark:/67375/HCB-2D3SH7CB-V</idno><idno type="DOI">10.1007/3-540-48321-7_27</idno></analytic><monogr><title level="m" type="main">Fundamentals of Computation Theory</title><title level="m" type="sub">12th International Symposium, FCT’99 Iaşi, Romania, August 30 - September 3, 1999 Proceedings</title><idno type="DOI">10.1007/3-540-48321-7</idno><idno type="book-id">3-540-48321-7</idno><idno type="ISBN">978-3-540-66412-3</idno><idno type="eISBN">978-3-540-48321-2</idno><idno type="chapter-id">Chap27</idno><editor><persName><forename type="first">Gabriel</forename><surname>Ciobanu</surname></persName><email>gabriel@info.uaic.ro</email><affiliation><orgName type="department">Faculty of Computer Science</orgName><orgName type="institution">“A.I.Cuza” University</orgName><address><postCode>6600</postCode><settlement>Iaşi</settlement><country key="RO">ROMANIA</country></address></affiliation></editor><editor><persName><forename type="first">Gheorghe</forename><surname>Păun</surname></persName><email>gpaun@imar.ro</email><affiliation><orgName type="institution">Institute of Mathematics of the Romanian Academy</orgName><address><postBox>P.O. Box 1-764</postBox><postCode>70700</postCode><settlement>Bucharest</settlement><country key="RO">ROMANIA</country></address></affiliation></editor><imprint><biblScope unit="vol">1684</biblScope><biblScope unit="page" from="327">327</biblScope><biblScope unit="page" to="337">337</biblScope><biblScope unit="chapter-count">47</biblScope></imprint></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName><affiliation><orgName type="institution">Karlsruhe University</orgName><address><country key="DE">GERMANY</country></address></affiliation></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName><affiliation><orgName type="institution">Cornell University</orgName><address><region>NY</region><country key="US">UNITED STATES</country></address></affiliation></editor><editor><persName><forename type="first">Jan</forename><nameLink>van</nameLink><surname>Leeuwen</surname></persName><affiliation><orgName type="institution">Utrecht University</orgName><address><country key=""></country></address></affiliation></editor><idno type="pISSN">0302-9743</idno><idno type="seriesID">558</idno></series></biblStruct></sourceDesc></fileDesc><profileDesc><abstract xml:lang="en"><head>Abstract</head><p>The unique satisfiability problem, that asks whether there exists a unique solution to a given propositional formula, was extensively studied in the recent years. This paper presents a dichotomy theorem for the unique satisfiability problem, partitioning the instances of the problem between the polynomial-time solvable and coNP-hard cases. We notice that the additional knowledge of a model makes this problem coNP-complete.We compare the polynomial cases of unique satisfiability to the polynomial cases of the usual satisfiability problem and show that they are incomparable. This difference between the polynomial cases is partially due to the necessity to apply parsimonious reductions among the unique satisfiability problems to preserve the number of solutions. In particular, we notice that the unique not-all-equal satisfiability problem, where we ask whether there is a unique model such that each clause has at least one true literal and one false literal, is solvable in polynomial time.</p></abstract><textClass ana="subject"><keywords scheme="book-subject-collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass ana="subject"><keywords scheme="book-subject"><list><label>I</label><item><term type="Primary">Computer Science</term></item><label>I16005</label><item><term type="Secondary" subtype="priority-1">Theory of Computation</term></item><label>I17028</label><item><term type="Secondary" subtype="priority-2">Discrete Mathematics in Computer Science</term></item><label>I15017</label><item><term type="Secondary" subtype="priority-3">Data Structures</term></item></list></keywords></textClass><langUsage><language ident="EN"></language></langUsage></profileDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-2D3SH7CB-V/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="corpus springer-ebooks not found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Karlsruhe University</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Cornell University</OrgName><OrgAddress><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>Utrecht University</OrgName><OrgAddress><Country>The Netherlands</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingStyle="Unnumbered" TocLevels="0"><BookID>3-540-48321-7</BookID><BookTitle>Fundamentals of Computation Theory</BookTitle><BookSubTitle>12th International Symposium, FCT’99 Iaşi, Romania, August 30 - September 3, 1999 Proceedings</BookSubTitle><BookVolumeNumber>1684</BookVolumeNumber><BookSequenceNumber>1684</BookSequenceNumber><BookDOI>10.1007/3-540-48321-7</BookDOI><BookTitleID>59698</BookTitleID><BookPrintISBN>978-3-540-66412-3</BookPrintISBN><BookElectronicISBN>978-3-540-48321-2</BookElectronicISBN><BookChapterCount>47</BookChapterCount><BookHistory><OnlineDate><Year>2003</Year><Month>6</Month><Day>3</Day></OnlineDate></BookHistory><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>1999</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16005" Priority="1" Type="Secondary">Theory of Computation</BookSubject><BookSubject Code="I17028" Priority="2" Type="Secondary">Discrete Mathematics in Computer Science</BookSubject><BookSubject Code="I15017" Priority="3" Type="Secondary">Data Structures</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Gabriel</GivenName><FamilyName>Ciobanu</FamilyName></EditorName><Contact><Email>gabriel@info.uaic.ro</Email></Contact></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Gheorghe</GivenName><FamilyName>Păun</FamilyName></EditorName><Contact><Email>gpaun@imar.ro</Email></Contact></Editor><Affiliation ID="Aff4"><OrgDivision>Faculty of Computer Science</OrgDivision><OrgName>“A.I.Cuza” University</OrgName><OrgAddress><Postcode>6600</Postcode><City>Iaşi</City><Country>Romania</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgName>Institute of Mathematics of the Romanian Academy</OrgName><OrgAddress><Postbox>P.O. Box 1-764</Postbox><Postcode>70700</Postcode><City>Bucharest</City><Country>Romania</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Chapter ID="Chap27" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" Language="En" NumberingStyle="Unnumbered" TocLevels="0"><ChapterID>27</ChapterID><ChapterDOI>10.1007/3-540-48321-7_27</ChapterDOI><ChapterSequenceNumber>27</ChapterSequenceNumber><ChapterTitle Language="En">Dichotomy theorem for the generalized unique satisfiability problem</ChapterTitle><ChapterFirstPage>327</ChapterFirstPage><ChapterLastPage>337</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>1999</CopyrightYear></ChapterCopyright><ChapterHistory><RegistrationDate><Year>2003</Year><Month>6</Month><Day>2</Day></RegistrationDate><OnlineDate><Year>2003</Year><Month>6</Month><Day>3</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3-540-48321-7</BookID><BookTitle>Fundamentals of Computation Theory</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff6"><AuthorName DisplayOrder="Western"><GivenName>Laurent</GivenName><FamilyName>Juban</FamilyName></AuthorName><Contact><Email>juban@loria.fr</Email></Contact></Author><Affiliation ID="Aff6"><OrgName>LORIA (Universitè Henri Poincarè Nancy 1)</OrgName><OrgAddress><Street>BP 239</Street><Postcode>54506</Postcode><City>Vandœuvre-lèes-Nancy</City><Country>France</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>The unique satisfiability problem, that asks whether there exists a unique solution to a given propositional formula, was extensively studied in the recent years. This paper presents a dichotomy theorem for the unique satisfiability problem, partitioning the instances of the problem between the polynomial-time solvable and coNP-hard cases. We notice that the additional knowledge of a model makes this problem coNP-complete.We compare the polynomial cases of unique satisfiability to the polynomial cases of the usual satisfiability problem and show that they are incomparable. This difference between the polynomial cases is partially due to the necessity to apply parsimonious reductions among the unique satisfiability problems to preserve the number of solutions. In particular, we notice that the unique not-all-equal satisfiability problem, where we ask whether there is a unique model such that each clause has at least one true literal and one false literal, is solvable in polynomial time.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Dichotomy theorem for the generalized unique satisfiability problem</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Dichotomy theorem for the generalized unique satisfiability problem</title></titleInfo><name type="personal"><namePart type="given">Laurent</namePart><namePart type="family">Juban</namePart><affiliation>LORIA (Universitè Henri Poincarè Nancy 1), BP 239, 54506, Vandœuvre-lèes-Nancy, France</affiliation><affiliation>E-mail: juban@loria.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre displayLabel="OriginalPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" type="conference" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-BFHXPBJJ-3">conference</genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">1999</dateIssued><copyrightDate encoding="w3cdtf">1999</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract: The unique satisfiability problem, that asks whether there exists a unique solution to a given propositional formula, was extensively studied in the recent years. This paper presents a dichotomy theorem for the unique satisfiability problem, partitioning the instances of the problem between the polynomial-time solvable and coNP-hard cases. We notice that the additional knowledge of a model makes this problem coNP-complete.We compare the polynomial cases of unique satisfiability to the polynomial cases of the usual satisfiability problem and show that they are incomparable. This difference between the polynomial cases is partially due to the necessity to apply parsimonious reductions among the unique satisfiability problems to preserve the number of solutions. In particular, we notice that the unique not-all-equal satisfiability problem, where we ask whether there is a unique model such that each clause has at least one true literal and one false literal, is solvable in polynomial time.</abstract><relatedItem type="host"><titleInfo><title>Fundamentals of Computation Theory</title><subTitle>12th International Symposium, FCT’99 Iaşi, Romania, August 30 - September 3, 1999 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Gabriel</namePart><namePart type="family">Ciobanu</namePart><affiliation>Faculty of Computer Science, “A.I.Cuza” University, 6600, Iaşi, Romania</affiliation><affiliation>E-mail: gabriel@info.uaic.ro</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gheorghe</namePart><namePart type="family">Păun</namePart><affiliation>Institute of Mathematics of the Romanian Academy, P.O. Box 1-764, 70700, Bucharest, Romania</affiliation><affiliation>E-mail: gpaun@imar.ro</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0G6R5W5T-Z">book-series</genre><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">1999</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16005">Theory of Computation</topic><topic authority="SpringerSubjectCodes" authorityURI="I17028">Discrete Mathematics in Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I15017">Data Structures</topic></subject><identifier type="DOI">10.1007/3-540-48321-7</identifier><identifier type="ISBN">978-3-540-66412-3</identifier><identifier type="eISBN">978-3-540-48321-2</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="BookTitleID">59698</identifier><identifier type="BookID">3-540-48321-7</identifier><identifier type="BookChapterCount">47</identifier><identifier type="BookVolumeNumber">1684</identifier><identifier type="BookSequenceNumber">1684</identifier><part><date>1999</date><detail type="volume"><number>1684</number><caption>vol.</caption></detail><extent unit="pages"><start>327</start><end>337</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 1999</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><affiliation>Karlsruhe University, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><affiliation>Cornell University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><affiliation>Utrecht University, The Netherlands</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><publisher>Springer</publisher><copyrightDate encoding="w3cdtf">1999</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 1999</recordOrigin></recordInfo></relatedItem><identifier type="istex">36A26C2FA4AFB12688D7EC9C12827C7CB7C8AD4B</identifier><identifier type="ark">ark:/67375/HCB-2D3SH7CB-V</identifier><identifier type="DOI">10.1007/3-540-48321-7_27</identifier><identifier type="ChapterID">27</identifier><identifier type="ChapterID">Chap27</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 1999</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-RLRX46XW-4">springer</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 1999</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/HCB-2D3SH7CB-V/record.json</uri></json:item></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C86 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000C86 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:36A26C2FA4AFB12688D7EC9C12827C7CB7C8AD4B
|texte= Dichotomy theorem for the generalized unique satisfiability problem
}}
| This area was generated with Dilib version V0.6.33. |  |