请输入您要查询的字词:

 

单词 PolynomialHierarchy
释义

polynomial hierarchy


The polynomial hierarchy is a hierarchy of complexity classesPlanetmathPlanetmath generalizing the relationship between 𝒫 and 𝒩𝒫.

We let Σ0p=Π0p=Δ0p=𝒫, then Δi+1p=𝒫Σip and Σi+1p=𝒩𝒫Σip. Define Πip to be coΣip.

For instance Σ1p=𝒩𝒫𝒫=𝒩𝒫.

The complexity class 𝒫=iΣip.

The polynomial hierarchy is closely related to the arithmetical hierarchy; indeed, an alternate definition is almost identical to the definition of the arithmetical hierarchy but stricter rules on what quantifiersMathworldPlanetmath can be used.

When there is no risk of confusion with the arithmetical hierarchy, the superscript p can be dropped.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 13:48:10