| http://dbpedia.org/ontology/abstract
|
Na Teoria da Computação, uma redução em es … Na Teoria da Computação, uma redução em espaço logaritmico, é uma redução computável por uma maquina de Turing deterministica usando espaço logarítmico. Conceitualmente, isso significa que ela pode manter uma número constante de ponteiros para a entrada, junto com um número logaritmico de inteiros de tamanho fixo. Já que tal máquina possui uma quantidade polinomial de configurações possíveis, reduções de espaço logaritmico são também reduções de tempo polinomiais. são também reduções de tempo polinomiais.
, 対数領域還元（たいすうりょういきかんげん、英: Log-space reductio … 対数領域還元（たいすうりょういきかんげん、英: Log-space reduction）は、計算複雑性理論において、決定性チューリング機械で対数領域を使って計算可能な還元である。概念的には、入力を一定数のポインタで指すことで、固定の対数領域だけを使用する。そのような機械の構成は多項式的に多数存在するので、対数領域還元は多項式時間還元でもある。 対数領域還元は多項式時間還元よりも弱いと考えられ、P に属する空でなく全体でもない言語は、P に属する別の空でなく全体でない言語に多項式時間還元可能だが、NL に属する言語とL に属する言語（共に P に包含される）との間の対数領域還元は L = NL ではないことを暗に示している。NP完全問題が、対数領域還元と多項式時間還元において異なるかどうかは未解決の問題である。 対数領域還元は P に属する言語について使われることが多く、それが多対一還元なのかチューリング還元なのかは問題とされないことが多い。なぜなら、L、SL、NL、P はチューリング還元において閉じており、チューリング還元を施すことで問題がそれらのクラスに属することを示すことが可能であるからである。しかし、NC も P に包含されるが、チューリング還元において閉じていないため、多対一還元を使わなければならない。 多項式時間還元が P やそのサブクラスではあまり意味がないのと同様、対数領域還元も L とそのサブクラスを区別するのには役立たない。L に属するほとんどの問題は、対数領域還元の下でL完全である。より弱い還元があったとしても、単に問題を L の真部分集合である言語に先延ばしするだけであるため、実際には使われることはほとんどない。 対数領域還元のためのツールは、L = SL という結果によって大きく拡張されてきた。SL完全問題は、今では対数領域還元のサブルーチンとして利用されている。張されてきた。SL完全問題は、今では対数領域還元のサブルーチンとして利用されている。
, Eine logarithmisch platzbeschränkte Redukt … Eine logarithmisch platzbeschränkte Reduktion (auch als logarithmische Reduktion bezeichnet) ist eine spezielle Form der Reduktion. Neben der Forderung, dass eine Sprache auf eine andere Sprache mittels einer Funktion reduzierbar ist, muss diese Funktion für eine logarithmische Reduktion zusätzlich auflogarithmischem Platz berechnet werden können. Logarithmische Reduktionen werden in der Komplexitätstheorie üblicherweise verwendet, um nachzuweisen, dass eine Sprache der Komplexitätsklasse NL auch NL-vollständig ist. Als Schreibweise wird hierbei häufig verwendet. Man beachte, dass für diese Reduktion die Transitivität gezeigt werden kann. Nur dadurch kann man mit diesem Begriff arbeiten.urch kann man mit diesem Begriff arbeiten.
, In computational complexity theory, a log- … In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a logarithmic number of fixed-size integers. It is possible that such a machine may not have space to write down its own output, so the only requirement is that any given bit of the output be computable in log-space. Formally, this reduction is executed via a log-space transducer. Such a machine has polynomially-many configurations, so log-space reductions are also polynomial-time reductions. However, log-space reductions are probably weaker than polynomial-time reductions; while any non-empty, non-full language in P is polynomial-time reducible to any other non-empty, non-full language in P, a log-space reduction from an NL-complete language to a language in L, both of which would be languages in P, would imply the unlikely L = NL. It is an open question if the NP-complete problems are different with respect to log-space and polynomial-time reductions. Log-space reductions are normally used on languages in P, in which case it usually does not matter whether many-one reductions or Turing reductions are used, since it has been verified that L, SL, NL, and P are all closed under Turing reductions, meaning that Turing reductions can be used to show a problem is in any of these classes. However, other subclasses of P such as NC may not be closed under Turing reductions, and so many-one reductions must be used. Just as polynomial-time reductions are useless within P and its subclasses, log-space reductions are useless to distinguish problems in L and its subclasses; in particular, every non-empty, non-full problem in L is trivially L-complete under log-space reductions. While even weaker reductions exist, they are not often used in practice, because complexity classes smaller than L (that is, strictly contained or thought to be strictly contained in L) receive relatively little attention. The tools available to designers of log-space reductions have been greatly expanded by the result that L = SL; see SL for a list of some SL-complete problems that can now be used as subroutines in log-space reductions.ed as subroutines in log-space reductions.
, En théorie de la complexité, une réduction en espace logarithmique est une réduction calculable par une machine de Turing disposant d'un espace de travail logarithmique.
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
https://archive.org/details/computationalcom00papa +
, https://archive.org/details/computationalcom00papa/page/n167 +
|
| http://dbpedia.org/ontology/wikiPageID
|
1174850
|
| http://dbpedia.org/ontology/wikiPageLength
|
3528
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1031189989
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/P_%28complexity%29 +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Turing_reduction +
, http://dbpedia.org/resource/Integer +
, http://dbpedia.org/resource/Many-one_reduction +
, http://dbpedia.org/resource/Category:Reduction_%28complexity%29 +
, http://dbpedia.org/resource/Polynomial-time_reduction +
, http://dbpedia.org/resource/Log-space_transducer +
, http://dbpedia.org/resource/Deterministic_Turing_machine +
, http://dbpedia.org/resource/Cambridge_University_Press +
, http://dbpedia.org/resource/Pointer_%28computer_programming%29 +
, http://dbpedia.org/resource/Reduction_%28complexity%29 +
, http://dbpedia.org/resource/SL_%28complexity%29 +
, http://dbpedia.org/resource/Complete_%28complexity%29 +
, http://dbpedia.org/resource/NC_%28complexity%29 +
, http://dbpedia.org/resource/NL_%28complexity%29 +
, http://dbpedia.org/resource/Logarithmic_space +
, http://dbpedia.org/resource/Computational_complexity_theory +
, http://dbpedia.org/resource/L_%28complexity%29 +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Citation_needed +
, http://dbpedia.org/resource/Template:Cite_book +
, http://dbpedia.org/resource/Template:Refimprove +
, http://dbpedia.org/resource/Template:Comp-sci-theory-stub +
, http://dbpedia.org/resource/Template:Reflist +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Reduction_%28complexity%29 +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Reduction +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Log-space_reduction?oldid=1031189989&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Log-space_reduction +
|
| owl:sameAs |
http://fr.dbpedia.org/resource/R%C3%A9duction_en_espace_logarithmique +
, http://www.wikidata.org/entity/Q448582 +
, http://ja.dbpedia.org/resource/%E5%AF%BE%E6%95%B0%E9%A0%98%E5%9F%9F%E9%82%84%E5%85%83 +
, http://zh.dbpedia.org/resource/Log-%E7%A9%BA%E9%97%B4%E8%A7%84%E7%BA%A6 +
, https://global.dbpedia.org/id/49ofU +
, http://pt.dbpedia.org/resource/Redu%C3%A7%C3%A3o_em_espa%C3%A7o_logar%C3%ADtmico +
, http://dbpedia.org/resource/Log-space_reduction +
, http://rdf.freebase.com/ns/m.04djlk +
, http://de.dbpedia.org/resource/Logarithmisch_platzbeschr%C3%A4nkte_Reduktion +
|
| rdf:type |
http://dbpedia.org/ontology/Album +
|
| rdfs:comment |
対数領域還元（たいすうりょういきかんげん、英: Log-space reductio … 対数領域還元（たいすうりょういきかんげん、英: Log-space reduction）は、計算複雑性理論において、決定性チューリング機械で対数領域を使って計算可能な還元である。概念的には、入力を一定数のポインタで指すことで、固定の対数領域だけを使用する。そのような機械の構成は多項式的に多数存在するので、対数領域還元は多項式時間還元でもある。 対数領域還元は多項式時間還元よりも弱いと考えられ、P に属する空でなく全体でもない言語は、P に属する別の空でなく全体でない言語に多項式時間還元可能だが、NL に属する言語とL に属する言語（共に P に包含される）との間の対数領域還元は L = NL ではないことを暗に示している。NP完全問題が、対数領域還元と多項式時間還元において異なるかどうかは未解決の問題である。 対数領域還元は P に属する言語について使われることが多く、それが多対一還元なのかチューリング還元なのかは問題とされないことが多い。なぜなら、L、SL、NL、P はチューリング還元において閉じており、チューリング還元を施すことで問題がそれらのクラスに属することを示すことが可能であるからである。しかし、NC も P に包含されるが、チューリング還元において閉じていないため、多対一還元を使わなければならない。れるが、チューリング還元において閉じていないため、多対一還元を使わなければならない。
, Na Teoria da Computação, uma redução em es … Na Teoria da Computação, uma redução em espaço logaritmico, é uma redução computável por uma maquina de Turing deterministica usando espaço logarítmico. Conceitualmente, isso significa que ela pode manter uma número constante de ponteiros para a entrada, junto com um número logaritmico de inteiros de tamanho fixo. Já que tal máquina possui uma quantidade polinomial de configurações possíveis, reduções de espaço logaritmico são também reduções de tempo polinomiais. são também reduções de tempo polinomiais.
, Eine logarithmisch platzbeschränkte Redukt … Eine logarithmisch platzbeschränkte Reduktion (auch als logarithmische Reduktion bezeichnet) ist eine spezielle Form der Reduktion. Neben der Forderung, dass eine Sprache auf eine andere Sprache mittels einer Funktion reduzierbar ist, muss diese Funktion für eine logarithmische Reduktion zusätzlich auflogarithmischem Platz berechnet werden können. Logarithmische Reduktionen werden in der Komplexitätstheorie üblicherweise verwendet, um nachzuweisen, dass eine Sprache der Komplexitätsklasse NL auch NL-vollständig ist. Als Schreibweise wird hierbei häufig verwendet.chreibweise wird hierbei häufig verwendet.
, En théorie de la complexité, une réduction en espace logarithmique est une réduction calculable par une machine de Turing disposant d'un espace de travail logarithmique.
, In computational complexity theory, a log- … In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a logarithmic number of fixed-size integers. It is possible that such a machine may not have space to write down its own output, so the only requirement is that any given bit of the output be computable in log-space. Formally, this reduction is executed via a log-space transducer.on is executed via a log-space transducer.
|
| rdfs:label |
Log-空间规约
, Réduction en espace logarithmique
, Redução em espaço logarítmico
, 対数領域還元
, Logarithmisch platzbeschränkte Reduktion
, Log-space reduction
|
