Reductions in Computational Complexity Using Clifford Algebras
Identifieur interne : 003C25 ( Istex/Corpus ); précédent : 003C24; suivant : 003C26Reductions in Computational Complexity Using Clifford Algebras
Auteurs : René Schott ; G. Stacey StaplesSource :
- Advances in Applied Clifford Algebras [ 0188-7009 ] ; 2010-03-01.
Abstract
Abstract.: A number of combinatorial problems are treated using properties of abelian null-square-generated and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of Λk, where Λ is an appropriate nilpotent adjacency matrix, the k-cycles in any finite graph are recovered. Within the algebra context (i.e., considering the number of multiplications performed within the algebra), these problems are reduced to matrix multiplication, which is in complexity class P. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and #P-complete to class P in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph.
Url:
DOI: 10.1007/s00006-008-0143-2
Links to Exploration step
ISTEX:FB4E52678311DC7B5D90BD784BC31849AD861BFELe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Reductions in Computational Complexity Using Clifford Algebras</title><author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name><affiliation><mods:affiliation>IECN and LORIA Université Henri Poincaré-Nancy I, BP 239, 54506, Vandoeuvre-lès-Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: schott@loria.fr</mods:affiliation></affiliation></author><author><name sortKey="Stacey Staples, G" sort="Stacey Staples, G" uniqKey="Stacey Staples G" first="G." last="Stacey Staples">G. Stacey Staples</name><affiliation><mods:affiliation>Department of Mathematics and Statistics, Southern Illinois University at Edwardsville, 62026-1653, Edwardsville, IL, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: sstaple@siue.edu</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:FB4E52678311DC7B5D90BD784BC31849AD861BFE</idno><date when="2008" year="2008">2008</date><idno type="doi">10.1007/s00006-008-0143-2</idno><idno type="url">https://api.istex.fr/ark:/67375/VQC-BX6194Q0-P/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">003C25</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003C25</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Reductions in Computational Complexity Using Clifford Algebras</title><author><name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name><affiliation><mods:affiliation>IECN and LORIA Université Henri Poincaré-Nancy I, BP 239, 54506, Vandoeuvre-lès-Nancy, France</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: schott@loria.fr</mods:affiliation></affiliation></author><author><name sortKey="Stacey Staples, G" sort="Stacey Staples, G" uniqKey="Stacey Staples G" first="G." last="Stacey Staples">G. Stacey Staples</name><affiliation><mods:affiliation>Department of Mathematics and Statistics, Southern Illinois University at Edwardsville, 62026-1653, Edwardsville, IL, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: sstaple@siue.edu</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Advances in Applied Clifford Algebras</title><title level="j" type="abbrev">AACA</title><idno type="ISSN">0188-7009</idno><idno type="eISSN">1661-4909</idno><imprint><publisher>Birkhäuser-Verlag; www.birkhäuser.ch</publisher><pubPlace>Basel</pubPlace><date type="published" when="2010-03-01">2010-03-01</date><biblScope unit="volume">20</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="121">121</biblScope><biblScope unit="page" to="140">140</biblScope></imprint><idno type="ISSN">0188-7009</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0188-7009</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract.: A number of combinatorial problems are treated using properties of abelian null-square-generated and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of Λk, where Λ is an appropriate nilpotent adjacency matrix, the k-cycles in any finite graph are recovered. Within the algebra context (i.e., considering the number of multiplications performed within the algebra), these problems are reduced to matrix multiplication, which is in complexity class P. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and #P-complete to class P in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph.</div></front></TEI><istex><corpusName>springer-journals</corpusName><author><json:item><name>René Schott</name><affiliations><json:string>IECN and LORIA Université Henri Poincaré-Nancy I, BP 239, 54506, Vandoeuvre-lès-Nancy, France</json:string><json:string>E-mail: schott@loria.fr</json:string></affiliations></json:item><json:item><name>G. Stacey Staples</name><affiliations><json:string>Department of Mathematics and Statistics, Southern Illinois University at Edwardsville, 62026-1653, Edwardsville, IL, USA</json:string><json:string>E-mail: sstaple@siue.edu</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Hamiltonian cycles</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>travelling salesman problem</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>longest path</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>NP-hard</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>NP-complete</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>cycle cover</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>set packing problem</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>set covering problem</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>matrix permanent</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>quantum computing</value></json:item></subject><articleId><json:string>143</json:string><json:string>s00006-008-0143-2</json:string></articleId><arkIstex>ark:/67375/VQC-BX6194Q0-P</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract.: A number of combinatorial problems are treated using properties of abelian null-square-generated and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of Λk, where Λ is an appropriate nilpotent adjacency matrix, the k-cycles in any finite graph are recovered. Within the algebra context (i.e., considering the number of multiplications performed within the algebra), these problems are reduced to matrix multiplication, which is in complexity class P. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and #P-complete to class P in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph.</abstract><qualityIndicators><score>8.776</score><pdfWordCount>6301</pdfWordCount><pdfCharCount>34159</pdfCharCount><pdfVersion>1.3</pdfVersion><pdfPageCount>20</pdfPageCount><pdfPageSize>592 x 842 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>148</abstractWordCount><abstractCharCount>1002</abstractCharCount><keywordCount>10</keywordCount></qualityIndicators><title>Reductions in Computational Complexity Using Clifford Algebras</title><genre><json:string>research-article</json:string></genre><host><title>Advances in Applied Clifford Algebras</title><language><json:string>unknown</json:string></language><publicationDate>2010</publicationDate><copyrightDate>2010</copyrightDate><issn><json:string>0188-7009</json:string></issn><eissn><json:string>1661-4909</json:string></eissn><journalId><json:string>6</json:string></journalId><volume>20</volume><issue>1</issue><pages><first>121</first><last>140</last></pages><genre><json:string>journal</json:string></genre><subject><json:item><value>Physics</value></json:item><json:item><value>Mathematical Methods in Physics</value></json:item><json:item><value>Theoretical, Mathematical and Computational Physics</value></json:item><json:item><value>Applications of Mathematics</value></json:item><json:item><value>Physics, general</value></json:item></subject></host><ark><json:string>ark:/67375/VQC-BX6194Q0-P</json:string></ark><publicationDate>2010</publicationDate><copyrightDate>2008</copyrightDate><doi><json:string>10.1007/s00006-008-0143-2</json:string></doi><id>FB4E52678311DC7B5D90BD784BC31849AD861BFE</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-BX6194Q0-P/fulltext.pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-BX6194Q0-P/bundle.zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/ark:/67375/VQC-BX6194Q0-P/fulltext.tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Reductions in Computational Complexity Using Clifford Algebras</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher scheme="https://scientific-publisher.data.istex.fr">Birkhäuser-Verlag; www.birkhäuser.ch</publisher><pubPlace>Basel</pubPlace><availability><licence><p>Birkhäuser Verlag Basel/Switzerland, 2008</p></licence><p scheme="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</p></availability><date>2008</date></publicationStmt><notesStmt><note type="research-article" scheme="https://content-type.data.istex.fr/ark:/67375/XTP-1JC4F85T-7">research-article</note><note type="journal" scheme="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Reductions in Computational Complexity Using Clifford Algebras</title><author xml:id="author-0000" corresp="yes"><persName><forename type="first">René</forename><surname>Schott</surname></persName><email>schott@loria.fr</email><affiliation>IECN and LORIA Université Henri Poincaré-Nancy I, BP 239, 54506, Vandoeuvre-lès-Nancy, France</affiliation></author><author xml:id="author-0001"><persName><forename type="first">G.</forename><surname>Stacey Staples</surname></persName><email>sstaple@siue.edu</email><affiliation>Department of Mathematics and Statistics, Southern Illinois University at Edwardsville, 62026-1653, Edwardsville, IL, USA</affiliation></author><idno type="istex">FB4E52678311DC7B5D90BD784BC31849AD861BFE</idno><idno type="ark">ark:/67375/VQC-BX6194Q0-P</idno><idno type="DOI">10.1007/s00006-008-0143-2</idno><idno type="article-id">143</idno><idno type="article-id">s00006-008-0143-2</idno></analytic><monogr><title level="j">Advances in Applied Clifford Algebras</title><title level="j" type="abbrev">AACA</title><idno type="pISSN">0188-7009</idno><idno type="eISSN">1661-4909</idno><idno type="journal-ID">true</idno><idno type="volume-issue-count">4</idno><imprint><publisher>Birkhäuser-Verlag; www.birkhäuser.ch</publisher><pubPlace>Basel</pubPlace><date type="published" when="2010-03-01"></date><biblScope unit="volume">20</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="121">121</biblScope><biblScope unit="page" to="140">140</biblScope></imprint></monogr></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2008</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract.: A number of combinatorial problems are treated using properties of abelian null-square-generated and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of Λk, where Λ is an appropriate nilpotent adjacency matrix, the k-cycles in any finite graph are recovered. Within the algebra context (i.e., considering the number of multiplications performed within the algebra), these problems are reduced to matrix multiplication, which is in complexity class P. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and #P-complete to class P in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph.</p></abstract><textClass xml:lang="--"><keywords scheme="keyword"><list><head>Keywords.</head><item><term>Hamiltonian cycles</term></item><item><term>travelling salesman problem</term></item><item><term>longest path</term></item><item><term>NP-hard</term></item><item><term>NP-complete</term></item><item><term>cycle cover</term></item><item><term>set packing problem</term></item><item><term>set covering problem</term></item><item><term>matrix permanent</term></item><item><term>quantum computing</term></item></list></keywords></textClass><textClass><classCode scheme="Mathematics Subject Classification (2000).">68Q15</classCode><classCode scheme="Mathematics Subject Classification (2000).">05C50</classCode><classCode scheme="Mathematics Subject Classification (2000).">05C38</classCode><classCode scheme="Mathematics Subject Classification (2000).">60B99</classCode><classCode scheme="Mathematics Subject Classification (2000).">81P68</classCode></textClass><textClass><keywords scheme="Journal-Subject-Group"><list><label>P</label><item><term>Physics</term></item><label>P19013</label><item><term>Mathematical Methods in Physics</term></item><label>P19005</label><item><term>Theoretical, Mathematical and Computational Physics</term></item><label>M13003</label><item><term>Applications of Mathematics</term></item><label>P00002</label><item><term>Physics, general</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2010-03-01">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-BX6194Q0-P/fulltext.txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="corpus springer-journals 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>Birkhäuser-Verlag</PublisherName><PublisherLocation>Basel</PublisherLocation><PublisherURL>www.birkhäuser.ch</PublisherURL></PublisherInfo><Journal><JournalInfo JournalProductType="ArchiveJournal" NumberingStyle="Unnumbered"><JournalID>6</JournalID><JournalPrintISSN>0188-7009</JournalPrintISSN><JournalElectronicISSN>1661-4909</JournalElectronicISSN><JournalTitle>Advances in Applied Clifford Algebras</JournalTitle><JournalAbbreviatedTitle>AACA</JournalAbbreviatedTitle><JournalSubjectGroup><JournalSubject Type="Primary" Code="P">Physics</JournalSubject><JournalSubject Type="Secondary" Priority="1" Code="P19013">Mathematical Methods in Physics</JournalSubject><JournalSubject Type="Secondary" Priority="2" Code="P19005">Theoretical, Mathematical and Computational Physics</JournalSubject><JournalSubject Type="Secondary" Priority="3" Code="M13003">Applications of Mathematics</JournalSubject><JournalSubject Type="Secondary" Priority="4" Code="P00002">Physics, general</JournalSubject></JournalSubjectGroup></JournalInfo><Volume><VolumeInfo VolumeType="Regular" TocLevels="0"><VolumeIDStart>20</VolumeIDStart><VolumeIDEnd>20</VolumeIDEnd><VolumeIssueCount>4</VolumeIssueCount></VolumeInfo><Issue IssueType="Regular" OutputMedium="All"><IssueInfo TocLevels="0"><IssueIDStart>1</IssueIDStart><IssueIDEnd>1</IssueIDEnd><IssueHistory><CoverDate><Year>2010</Year><Month>03</Month></CoverDate></IssueHistory><IssueCopyright><CopyrightHolderName>Birkhäuser / Springer Basel AG, Switzerland</CopyrightHolderName><CopyrightYear>2010</CopyrightYear></IssueCopyright></IssueInfo><Article ID="s00006-008-0143-2"><ArticleInfo Language="En" ArticleType="OriginalPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ArticleID>143</ArticleID><ArticleDOI>10.1007/s00006-008-0143-2</ArticleDOI><ArticleSequenceNumber>11</ArticleSequenceNumber><ArticleTitle Language="En" OutputMedium="All">Reductions in Computational Complexity Using Clifford Algebras</ArticleTitle><ArticleFirstPage>121</ArticleFirstPage><ArticleLastPage>140</ArticleLastPage><ArticleHistory><RegistrationDate><Year>2008</Year><Month>1</Month><Day>1</Day></RegistrationDate><OnlineDate><Year>2008</Year><Month>12</Month><Day>11</Day></OnlineDate></ArticleHistory><ArticleCopyright><CopyrightHolderName>Birkhäuser Verlag Basel/Switzerland</CopyrightHolderName><CopyrightYear>2008</CopyrightYear></ArticleCopyright><ArticleGrants 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></ArticleGrants></ArticleInfo><ArticleHeader><AuthorGroup><Author AffiliationIDS="Aff1" CorrespondingAffiliationID="Aff1"><AuthorName DisplayOrder="Western"><GivenName>René</GivenName><FamilyName>Schott</FamilyName></AuthorName><Contact><Email>schott@loria.fr</Email></Contact></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>G.</GivenName><FamilyName>Stacey Staples</FamilyName></AuthorName><Contact><Email>sstaple@siue.edu</Email></Contact></Author><Affiliation ID="Aff1"><OrgName>IECN and LORIA Université Henri Poincaré-Nancy I</OrgName><OrgAddress><Postbox>BP 239</Postbox><Postcode>54506</Postcode><City>Vandoeuvre-lès-Nancy</City><Country Code="FR">France</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Department of Mathematics and Statistics</OrgDivision><OrgName>Southern Illinois University at Edwardsville</OrgName><OrgAddress><City>Edwardsville</City><State>IL</State><Postcode>62026-1653</Postcode><Country Code="US">USA</Country></OrgAddress></Affiliation></AuthorGroup><Abstract Language="En" ID="Abs1"><Heading>Abstract.</Heading><Para>A number of combinatorial problems are treated using properties of abelian null-square-generated and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of Λ<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>, where Λ is an appropriate nilpotent adjacency matrix, the <Emphasis Type="Italic">k</Emphasis>-cycles in any finite graph are recovered. Within the algebra context (i.e., considering the number of multiplications performed within the algebra), these problems are reduced to matrix multiplication, which is in complexity class P. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and #P-complete to class P in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph.</Para></Abstract><KeywordGroup Language="En"><Heading>Mathematics Subject Classification (2000).</Heading><Keyword>68Q15</Keyword><Keyword>05C50</Keyword><Keyword>05C38</Keyword><Keyword>60B99</Keyword><Keyword>81P68</Keyword></KeywordGroup><KeywordGroup Language="--"><Heading>Keywords.</Heading><Keyword>Hamiltonian cycles</Keyword><Keyword>travelling salesman problem</Keyword><Keyword>longest path</Keyword><Keyword>NP-hard</Keyword><Keyword>NP-complete</Keyword><Keyword>cycle cover</Keyword><Keyword>set packing problem</Keyword><Keyword>set covering problem</Keyword><Keyword>matrix permanent</Keyword><Keyword>quantum computing</Keyword></KeywordGroup><ArticleNote Type="Misc"><SimplePara>A preliminary version of this paper has been presented at AGACSE 2008 (3rd International Conference on Applied Geometric Algebras in Computer Science and Engineering).</SimplePara></ArticleNote><ArticleNote Type="Misc"><SimplePara>Received: July 4, 2008. Accepted: October 1, 2008.</SimplePara></ArticleNote></ArticleHeader><NoBody></NoBody></Article></Issue></Volume></Journal></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Reductions in Computational Complexity Using Clifford Algebras</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Reductions in Computational Complexity Using Clifford Algebras</title></titleInfo><name type="personal" displayLabel="corresp"><namePart type="given">René</namePart><namePart type="family">Schott</namePart><affiliation>IECN and LORIA Université Henri Poincaré-Nancy I, BP 239, 54506, Vandoeuvre-lès-Nancy, France</affiliation><affiliation>E-mail: schott@loria.fr</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">G.</namePart><namePart type="family">Stacey Staples</namePart><affiliation>Department of Mathematics and Statistics, Southern Illinois University at Edwardsville, 62026-1653, Edwardsville, IL, USA</affiliation><affiliation>E-mail: sstaple@siue.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="OriginalPaper" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-1JC4F85T-7">research-article</genre><originInfo><publisher>Birkhäuser-Verlag; www.birkhäuser.ch</publisher><place><placeTerm type="text">Basel</placeTerm></place><dateIssued encoding="w3cdtf">2010-03-01</dateIssued><copyrightDate encoding="w3cdtf">2008</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><abstract lang="en">Abstract.: A number of combinatorial problems are treated using properties of abelian null-square-generated and idempotent-generated subalgebras of Clifford algebras. For example, the problem of deciding whether or not a graph contains a Hamiltonian cycle is known to be NP-complete. By considering entries of Λk, where Λ is an appropriate nilpotent adjacency matrix, the k-cycles in any finite graph are recovered. Within the algebra context (i.e., considering the number of multiplications performed within the algebra), these problems are reduced to matrix multiplication, which is in complexity class P. The Hamiltonian cycle problem is one of many problems moved from classes NP-complete and #P-complete to class P in this context. Other problems considered include the set covering problem, counting the edge-disjoint cycle decompositions of a finite graph, computing the permanent of an arbitrary matrix, computing the girth and circumference of a graph, and finding the longest path in a graph.</abstract><classification displayLabel="Mathematics Subject Classification (2000).">68Q15</classification><classification displayLabel="Mathematics Subject Classification (2000).">05C50</classification><classification displayLabel="Mathematics Subject Classification (2000).">05C38</classification><classification displayLabel="Mathematics Subject Classification (2000).">60B99</classification><classification displayLabel="Mathematics Subject Classification (2000).">81P68</classification><subject lang="--"><genre>Keywords.</genre><topic>Hamiltonian cycles</topic><topic>travelling salesman problem</topic><topic>longest path</topic><topic>NP-hard</topic><topic>NP-complete</topic><topic>cycle cover</topic><topic>set packing problem</topic><topic>set covering problem</topic><topic>matrix permanent</topic><topic>quantum computing</topic></subject><relatedItem type="host"><titleInfo><title>Advances in Applied Clifford Algebras</title></titleInfo><titleInfo type="abbreviated"><title>AACA</title></titleInfo><genre type="journal" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</genre><originInfo><publisher>Springer</publisher><dateIssued encoding="w3cdtf">2010-03-01</dateIssued><copyrightDate encoding="w3cdtf">2010</copyrightDate></originInfo><subject><genre>Journal-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="P">Physics</topic><topic authority="SpringerSubjectCodes" authorityURI="P19013">Mathematical Methods in Physics</topic><topic authority="SpringerSubjectCodes" authorityURI="P19005">Theoretical, Mathematical and Computational Physics</topic><topic authority="SpringerSubjectCodes" authorityURI="M13003">Applications of Mathematics</topic><topic authority="SpringerSubjectCodes" authorityURI="P00002">Physics, general</topic></subject><identifier type="ISSN">0188-7009</identifier><identifier type="eISSN">1661-4909</identifier><identifier type="JournalID">6</identifier><identifier type="VolumeIssueCount">4</identifier><part><date>2010</date><detail type="volume"><number>20</number><caption>vol.</caption></detail><detail type="issue"><number>1</number><caption>no.</caption></detail><extent unit="pages"><start>121</start><end>140</end></extent></part><recordInfo><recordOrigin>Birkhäuser / Springer Basel AG, Switzerland, 2010</recordOrigin></recordInfo></relatedItem><identifier type="istex">FB4E52678311DC7B5D90BD784BC31849AD861BFE</identifier><identifier type="ark">ark:/67375/VQC-BX6194Q0-P</identifier><identifier type="DOI">10.1007/s00006-008-0143-2</identifier><identifier type="ArticleID">143</identifier><identifier type="ArticleID">s00006-008-0143-2</identifier><accessCondition type="use and reproduction" contentType="copyright">Birkhäuser Verlag Basel/Switzerland, 2008</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-3XSW68JL-F">springer</recordContentSource><recordOrigin>Birkhäuser Verlag Basel/Switzerland, 2008</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/ark:/67375/VQC-BX6194Q0-P/record.json</uri></json:item></metadata><serie></serie></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 003C25 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 003C25 | 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:FB4E52678311DC7B5D90BD784BC31849AD861BFE
|texte= Reductions in Computational Complexity Using Clifford Algebras
}}
| This area was generated with Dilib version V0.6.33. |  |