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 N6513388b0d384d64bf364013e341557e
    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 N6033bb64661741efb1832de41cdd5dc1
    19 Ne98f56b43d9f4e6e96aef64a3dc54aa0
    20 sg:journal.1140079
    21 schema:name A Stochastic Limit Approach to the SAT Problem
    22 schema:pagination 219-233
    23 schema:productId Nb862c0f88e6440498026678d5b6edf96
    24 Nd076d160141f4c85b34852db6ae4fc21
    25 Nda1f8f34d2904be7972ab2739cf0fa67
    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 Nb7c7123dc731486daa65388e62d6aa7d
    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 N6033bb64661741efb1832de41cdd5dc1 schema:issueNumber 3
    36 rdf:type schema:PublicationIssue
    37 N6513388b0d384d64bf364013e341557e rdf:first sg:person.012602646421.58
    38 rdf:rest Ndf1ea0ffc950493aabddb30293a66ed3
    39 Nb7c7123dc731486daa65388e62d6aa7d schema:name Springer Nature - SN SciGraph project
    40 rdf:type schema:Organization
    41 Nb862c0f88e6440498026678d5b6edf96 schema:name dimensions_id
    42 schema:value pub.1051753591
    43 rdf:type schema:PropertyValue
    44 Nd076d160141f4c85b34852db6ae4fc21 schema:name readcube_id
    45 schema:value f686a7a7f5bf13be984586195800006509c51f53671c16d2a038641f4a3a37ed
    46 rdf:type schema:PropertyValue
    47 Nda1f8f34d2904be7972ab2739cf0fa67 schema:name doi
    48 schema:value 10.1023/b:opsy.0000047567.88377.74
    49 rdf:type schema:PropertyValue
    50 Ndf1ea0ffc950493aabddb30293a66ed3 rdf:first sg:person.013365420775.41
    51 rdf:rest rdf:nil
    52 Ne98f56b43d9f4e6e96aef64a3dc54aa0 schema:volumeNumber 11
    53 rdf:type schema:PublicationVolume
    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)


    ...