In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs. Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes nor no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Πρόβλημα υπόσχεσης (el)
- Promise problem (en)
- 承諾問題 (zh)
|
| rdfs:comment
| - In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs. Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes nor no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt. (en)
- 在計算複雜度理論裡，承諾問題是一類決定性問題，其可接受輸入是一個確定大小的集合。與其他的決定性問題不同，承諾問題接受的輸入（確定輸出會是是或者否的輸入）並不包含所有可能的輸入。直覺上，我們可以說輸入的承諾是在一群是的輸入或否的輸入裡面。如果輸入不屬於這兩個集合，那麼此演算法允許輸出任何答覆。 (zh)
- Στη θεωρία υπολογιστικής πολυπλοκότητας, ένα πρόβλημα υπόσχεσης είναι μια γενίκευση κάποιου προβλήματος απόφασης, για το οποίο μάς δίνεται η διαβεβαίωση ότι δέχεται εισόδους από ένα συγκεκριμένο υποσύνολο όλων των πιθανών εισόδων.Σε αντίθεση με τα προβλήματα απόφασης, τα ναι στιγμιότυπα (οι είσοδοι για τις οποίες ο αλγόριθμος πρέπει υποχρεωτικά να επιστρέψει ναι) και τα όχι στιγμιότυπα δεν εξαντλούν το σύνολο όλων των πιθανών εισόδων. Διαισθητικά, ο αλγόριθμος έχει λάβει τη διαβεβαίωση (υπόσχεση) ότι η είσοδος θα ανήκει σε κάποιο σύνολο ναι στιγμιοτύπων ή όχι στιγμιοτύπων. Μπορεί όμως να υπάρχουν και είσοδοι που δεν είναι ούτε ναι ούτε όχι. Εάν δοθεί στον αλγόριθμο μια τέτοια είσοδος για την επίλυση κάποιου προβλήματος υπόσχεσης, τότε αυτός μπορεί να επιστρέψει οτιδήποτε, ή ακόμα και να τε (el)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has abstract
| - Στη θεωρία υπολογιστικής πολυπλοκότητας, ένα πρόβλημα υπόσχεσης είναι μια γενίκευση κάποιου προβλήματος απόφασης, για το οποίο μάς δίνεται η διαβεβαίωση ότι δέχεται εισόδους από ένα συγκεκριμένο υποσύνολο όλων των πιθανών εισόδων.Σε αντίθεση με τα προβλήματα απόφασης, τα ναι στιγμιότυπα (οι είσοδοι για τις οποίες ο αλγόριθμος πρέπει υποχρεωτικά να επιστρέψει ναι) και τα όχι στιγμιότυπα δεν εξαντλούν το σύνολο όλων των πιθανών εισόδων. Διαισθητικά, ο αλγόριθμος έχει λάβει τη διαβεβαίωση (υπόσχεση) ότι η είσοδος θα ανήκει σε κάποιο σύνολο ναι στιγμιοτύπων ή όχι στιγμιοτύπων. Μπορεί όμως να υπάρχουν και είσοδοι που δεν είναι ούτε ναι ούτε όχι. Εάν δοθεί στον αλγόριθμο μια τέτοια είσοδος για την επίλυση κάποιου προβλήματος υπόσχεσης, τότε αυτός μπορεί να επιστρέψει οτιδήποτε, ή ακόμα και να τερματίσει. (el)
- In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs. Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes nor no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt. (en)
- 在計算複雜度理論裡，承諾問題是一類決定性問題，其可接受輸入是一個確定大小的集合。與其他的決定性問題不同，承諾問題接受的輸入（確定輸出會是是或者否的輸入）並不包含所有可能的輸入。直覺上，我們可以說輸入的承諾是在一群是的輸入或否的輸入裡面。如果輸入不屬於這兩個集合，那麼此演算法允許輸出任何答覆。 (zh)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)