This HTML5 document contains 36 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n14https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Alternating_Turing_machine
dbo:wikiPageWikiLink
dbr:Parallel_computation_thesis
Subject Item
dbr:List_of_terms_relating_to_algorithms_and_data_structures
dbo:wikiPageWikiLink
dbr:Parallel_computation_thesis
Subject Item
dbr:Parallel_Computation_Thesis
dbo:wikiPageWikiLink
dbr:Parallel_computation_thesis
dbo:wikiPageRedirects
dbr:Parallel_computation_thesis
Subject Item
dbr:Parallel_computation_thesis
rdfs:label
Tese da computação paralela Parallel computation thesis
rdfs:comment
In computational complexity theory, the parallel computation thesis is a hypothesis which states that the time used by a (reasonable) parallel machine is polynomially related to the space used by a sequential machine. The parallel computation thesis was set forth by Chandra and Stockmeyer in 1976. Na teoria da complexidade computacional, a tese da computação paralela é uma hipótese que afirma que o tempo é utilizado por uma máquina paralela (razoável) e é polinomialmente relacionada com o espaço utilizado por uma máquina seqüencial. A tese de computação paralela foi estabelecido por Chandra e Larry Stockmeyer em 1976 (ver Referências).
dcterms:subject
dbc:Theory_of_computation dbc:Parallel_computing
dbo:wikiPageID
3447712
dbo:wikiPageRevisionID
1000105101
dbo:wikiPageWikiLink
dbr:Ashok_K._Chandra dbc:Theory_of_computation dbr:Non-deterministic_Turing_machine dbr:Larry_Stockmeyer dbr:Formal_language dbr:Big_O_notation dbr:Turing_machine dbr:Computational_complexity_theory dbr:Hypothesis dbr:Alternating_Turing_machine dbr:Computational_model dbc:Parallel_computing dbr:Decidable_language
owl:sameAs
freebase:m.09cyjx dbpedia-pt:Tese_da_computação_paralela wikidata:Q7134997 n14:4tBmh
dbp:wikiPageUsesTemplate
dbt:Reflist
dbo:abstract
Na teoria da complexidade computacional, a tese da computação paralela é uma hipótese que afirma que o tempo é utilizado por uma máquina paralela (razoável) e é polinomialmente relacionada com o espaço utilizado por uma máquina seqüencial. A tese de computação paralela foi estabelecido por Chandra e Larry Stockmeyer em 1976 (ver Referências). Em outras palavras, é um modelo computacional que permite cálculos em ramificação e executados em paralelo sem limites, uma linguagem formal que é decidível sob o modelo usando não mais que passos para as entradas de comprimento n é decidível por uma máquina no modelo desramificação usando não mais que unidade de armazenamento para alguma constante k. Da mesma forma, se uma máquina no modelo de desramificação decide uma linguagem utilizando não mais do que armazenamento, uma máquina no modelo paralelo pode decidir a linguagem em não mais do que passos para alguma constante k. A tese de computação paralela não é uma declaração formal rigorosa, uma vez que não define claramente o que constitui um modelo aceitável paralelo. A máquina paralela deve ser suficientemente poderosa para emular a máquina seqüencial em tempo polinomial relacionadas com o espaço seqüencial; compare máquina de Turing, máquina de Turing não-determinística, e máquina de Turing alternada. Em 1983, N. Blum introduziu um modelo em que a tese não se sustenta. No entanto, o modelo permite processos de computação paralela após passos. (Veja notação Grande-O.) Em 1986, Parberry sugeriu uma forma mais "razoável" que seria ou , em defesa da tese. Em 1982, Goldschlager propôs um modelo que é suficientemente universal para emular todas os modelos paralelos "razoáveis", que aderem à tese. Chandra e Stockmeyer originalmente formalizaram e provaram resultados relacionadas com a tese para máquinas Turing determinísticas e alternadas, que é de onde se originou a tese. In computational complexity theory, the parallel computation thesis is a hypothesis which states that the time used by a (reasonable) parallel machine is polynomially related to the space used by a sequential machine. The parallel computation thesis was set forth by Chandra and Stockmeyer in 1976. In other words, for a computational model which allows computations to branch and run in parallel without bound, a formal language which is decidable under the model using no more than steps for inputs of length n is decidable by a non-branching machine using no more than units of storage for some constant k. Similarly, if a machine in the unbranching model decides a language using no more than storage, a machine in the parallel model can decide the language in no more than steps for some constant k. The parallel computation thesis is not a rigorous formal statement, as it does not clearly define what constitutes an acceptable parallel model. A parallel machine must be sufficiently powerful to emulate the sequential machine in time polynomially related to the sequential space; compare Turing machine, non-deterministic Turing machine, and alternating Turing machine. N. Blum (1983) introduced a model for which the thesis does not hold.However, the model allows parallel threads of computation after steps. (See Big O notation.) Parberry (1986) suggested a more "reasonable" bound would be or , in defense of the thesis.Goldschlager (1982) proposed a model which is sufficiently universal to emulate all "reasonable" parallel models, which adheres to the thesis.Chandra and Stockmeyer originally formalized and proved results related to the thesis for deterministic and alternating Turing machines, which is where the thesis originated.
prov:wasDerivedFrom
wikipedia-en:Parallel_computation_thesis?oldid=1000105101&ns=0
dbo:wikiPageLength
3327
foaf:isPrimaryTopicOf
wikipedia-en:Parallel_computation_thesis
Subject Item
wikipedia-en:Parallel_computation_thesis
foaf:primaryTopic
dbr:Parallel_computation_thesis