A Stochastic Limit Approach to the SAT Problem View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2004-09

AUTHORS

Luigi Accardi, Masanori Ohya

ABSTRACT

There exists an important problem whether there exists an algorithm to solve an NP-complete problem in polynomial time. In this paper, a new concept of quantum adaptive stochastic systems is proposed, and it is shown that it can be used to solve the problem above.

PAGES

219-233

References to SciGraph publications

  • 1998-01. Complexities and Their Applications to Characterization of Chaos in INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS
  • 2002. Quantum Theory and Its Stochastic Limit in NONE
  • 2003-09. How Can We Observe and Describe Chaos? in OPEN SYSTEMS AND INFORMATION DYNAMICS
  • 2000-03. NP Problem in Quantum Algorithm in OPEN SYSTEMS AND INFORMATION DYNAMICS
  • 1999-02. Compound Channels, Transition Expectations, and Liftings in APPLIED MATHEMATICS & OPTIMIZATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/b:opsy.0000047567.88377.74

    DOI

    http://dx.doi.org/10.1023/b:opsy.0000047567.88377.74

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1051753591


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Rome Tor Vergata", 
              "id": "https://www.grid.ac/institutes/grid.6530.0", 
              "name": [
                "Centro V. Volterra, Universit\u00e0 di Roma Torvergata, Via Orazio Raimondo, 00173, Roma, Italia"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Accardi", 
            "givenName": "Luigi", 
            "id": "sg:person.012602646421.58", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012602646421.58"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Tokyo University of Science", 
              "id": "https://www.grid.ac/institutes/grid.143643.7", 
              "name": [
                "Department of Information Sciences, Tokyo University of Science, 278-8510, Noda City, Chiba, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ohya", 
            "givenName": "Masanori", 
            "id": "sg:person.013365420775.41", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013365420775.41"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1103/physrevlett.81.3992", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003448521"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/physrevlett.81.3992", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003448521"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s002459900097", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006979639", 
              "https://doi.org/10.1007/s002459900097"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1009651417615", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012766077", 
              "https://doi.org/10.1023/a:1009651417615"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0034-4877(03)90002-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024115457"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1025123923519", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036899820", 
              "https://doi.org/10.1023/a:1025123923519"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1026620313483", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044316893", 
              "https://doi.org/10.1023/a:1026620313483"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1045763589", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-04929-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045763589", 
              "https://doi.org/10.1007/978-3-662-04929-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-04929-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045763589", 
              "https://doi.org/10.1007/978-3-662-04929-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1098/rspa.1985.0070", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053404391"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/revmodphys.68.733", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060839377"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1103/revmodphys.68.733", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1060839377"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2004-09", 
        "datePublishedReg": "2004-09-01", 
        "description": "There exists an important problem whether there exists an algorithm to solve an NP-complete problem in polynomial time. In this paper, a new concept of quantum adaptive stochastic systems is proposed, and it is shown that it can be used to solve the problem above.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/b:opsy.0000047567.88377.74", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1140079", 
            "issn": [
              "1230-1612", 
              "1573-1324"
            ], 
            "name": "Open Systems and Information Dynamics", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "11"
          }
        ], 
        "name": "A Stochastic Limit Approach to the SAT Problem", 
        "pagination": "219-233", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "f686a7a7f5bf13be984586195800006509c51f53671c16d2a038641f4a3a37ed"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/b:opsy.0000047567.88377.74"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1051753591"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/b:opsy.0000047567.88377.74", 
          "https://app.dimensions.ai/details/publication/pub.1051753591"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T00:15", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8695_00000508.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023%2FB%3AOPSY.0000047567.88377.74"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1023/b:opsy.0000047567.88377.74'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1023/b:opsy.0000047567.88377.74'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/b:opsy.0000047567.88377.74'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/b:opsy.0000047567.88377.74'


     

    This table displays all metadata directly associated to this object as RDF triples.

    97 TRIPLES      20 PREDICATES      35 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/b:opsy.0000047567.88377.74 schema:author Na4880efad3b642c1ada4127cca31b83c
    2 schema:citation sg:pub.10.1007/978-3-662-04929-7
    3 sg:pub.10.1007/s002459900097
    4 sg:pub.10.1023/a:1009651417615
    5 sg:pub.10.1023/a:1025123923519
    6 sg:pub.10.1023/a:1026620313483
    7 https://app.dimensions.ai/details/publication/pub.1045763589
    8 https://doi.org/10.1016/s0034-4877(03)90002-4
    9 https://doi.org/10.1098/rspa.1985.0070
    10 https://doi.org/10.1103/physrevlett.81.3992
    11 https://doi.org/10.1103/revmodphys.68.733
    12 schema:datePublished 2004-09
    13 schema:datePublishedReg 2004-09-01
    14 schema:description There exists an important problem whether there exists an algorithm to solve an NP-complete problem in polynomial time. In this paper, a new concept of quantum adaptive stochastic systems is proposed, and it is shown that it can be used to solve the problem above.
    15 schema:genre research_article
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N98187a43f6a8417f8f7c6918ac2c358c
    19 N9e5e18be47774a27923c15d1b6cffb82
    20 sg:journal.1140079
    21 schema:name A Stochastic Limit Approach to the SAT Problem
    22 schema:pagination 219-233
    23 schema:productId N05087a6bb31e434db43395c1eb2efd7e
    24 N3ddf03eb0e9e42339a97cf0303926d16
    25 N7903ba7652a542c58efb9ba95041e2fe
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051753591
    27 https://doi.org/10.1023/b:opsy.0000047567.88377.74
    28 schema:sdDatePublished 2019-04-11T00:15
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher N63e79e8899874ae6b8ebf16200dcb110
    31 schema:url http://link.springer.com/10.1023%2FB%3AOPSY.0000047567.88377.74
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset articles
    34 rdf:type schema:ScholarlyArticle
    35 N05087a6bb31e434db43395c1eb2efd7e schema:name dimensions_id
    36 schema:value pub.1051753591
    37 rdf:type schema:PropertyValue
    38 N3ddf03eb0e9e42339a97cf0303926d16 schema:name doi
    39 schema:value 10.1023/b:opsy.0000047567.88377.74
    40 rdf:type schema:PropertyValue
    41 N63e79e8899874ae6b8ebf16200dcb110 schema:name Springer Nature - SN SciGraph project
    42 rdf:type schema:Organization
    43 N7903ba7652a542c58efb9ba95041e2fe schema:name readcube_id
    44 schema:value f686a7a7f5bf13be984586195800006509c51f53671c16d2a038641f4a3a37ed
    45 rdf:type schema:PropertyValue
    46 N846b967cd0a64e6d80b6ed80e2c032da rdf:first sg:person.013365420775.41
    47 rdf:rest rdf:nil
    48 N98187a43f6a8417f8f7c6918ac2c358c schema:issueNumber 3
    49 rdf:type schema:PublicationIssue
    50 N9e5e18be47774a27923c15d1b6cffb82 schema:volumeNumber 11
    51 rdf:type schema:PublicationVolume
    52 Na4880efad3b642c1ada4127cca31b83c rdf:first sg:person.012602646421.58
    53 rdf:rest N846b967cd0a64e6d80b6ed80e2c032da
    54 sg:journal.1140079 schema:issn 1230-1612
    55 1573-1324
    56 schema:name Open Systems and Information Dynamics
    57 rdf:type schema:Periodical
    58 sg:person.012602646421.58 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
    59 schema:familyName Accardi
    60 schema:givenName Luigi
    61 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012602646421.58
    62 rdf:type schema:Person
    63 sg:person.013365420775.41 schema:affiliation https://www.grid.ac/institutes/grid.143643.7
    64 schema:familyName Ohya
    65 schema:givenName Masanori
    66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013365420775.41
    67 rdf:type schema:Person
    68 sg:pub.10.1007/978-3-662-04929-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045763589
    69 https://doi.org/10.1007/978-3-662-04929-7
    70 rdf:type schema:CreativeWork
    71 sg:pub.10.1007/s002459900097 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006979639
    72 https://doi.org/10.1007/s002459900097
    73 rdf:type schema:CreativeWork
    74 sg:pub.10.1023/a:1009651417615 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012766077
    75 https://doi.org/10.1023/a:1009651417615
    76 rdf:type schema:CreativeWork
    77 sg:pub.10.1023/a:1025123923519 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036899820
    78 https://doi.org/10.1023/a:1025123923519
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1023/a:1026620313483 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044316893
    81 https://doi.org/10.1023/a:1026620313483
    82 rdf:type schema:CreativeWork
    83 https://app.dimensions.ai/details/publication/pub.1045763589 schema:CreativeWork
    84 https://doi.org/10.1016/s0034-4877(03)90002-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024115457
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1098/rspa.1985.0070 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053404391
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1103/physrevlett.81.3992 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003448521
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1103/revmodphys.68.733 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060839377
    91 rdf:type schema:CreativeWork
    92 https://www.grid.ac/institutes/grid.143643.7 schema:alternateName Tokyo University of Science
    93 schema:name Department of Information Sciences, Tokyo University of Science, 278-8510, Noda City, Chiba, Japan
    94 rdf:type schema:Organization
    95 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
    96 schema:name Centro V. Volterra, Università di Roma Torvergata, Via Orazio Raimondo, 00173, Roma, Italia
    97 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...