概要と定義

ウィキペディア小見出し辞書

概要と定義

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/11 23:12 UTC 版)

「マンション」の記事における「概要と定義」の解説

マンションという語は、日本のデベロッパーが昭和30年代初めより、一部の限られた階層を対象に、公団住宅などとは一線を画した高級路線の集合住宅を、高級感をイメージするために「マンション」と銘打って売り出したことに由来するという。その後、対象とする層を広げて多様なものが開発・販売されるようになっても、「マンション」という呼び名が定着した。ただし、英語では、Mansionは主に豪邸を示す言葉であり、日本語で言うような「共同住宅」を意味する一般名詞として用いられることはほとんどない。イギリスではより限定的に、Mansion Houseといった場合は市長公邸、Mansion blockといった場合は高級なアパートを指す。

概要と定義

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/14 09:13 UTC 版)

「PCP (計算複雑性理論)」の記事における「概要と定義」の解説

計算複雑性理論において、PCP 系は対話型証明系の一種と見ることができ、証明者がメモリを持たない神託機械であり、検証者が多項式時間の乱択アルゴリズムである。ある言語に属する入力（すなわち答えがYES）の場合、検証者が確実に受理する神託（証明）が存在する。答えがNOの入力の場合、神託がどうであれ、検証者はそれを少なくとも1/2の確率で拒絶する（co-RP参照）。 PCP の別の見方として、NP の強力版と見ることもできる。NPに属する言語について、証明の検証にかかる時間は少なくとも証明にかかる時間程度であるが、PCPに属する言語ではその限りではない。従って、PCPについての証明はNPよりも長くなる可能性がある。 上記の解説では、検証者が神託機械に問い合わせできる回数の上限を特に設定していない。PCP系の能力に影響するもう1つの要因として、検証者が実施できるコイントス回数がある。また、コイントス回数が増えれば、検証者はより厳密に証明を検証できる。従って PCP は実際には、2つの引数を持つ関数でパラメータ化された複雑性クラスのメタクラスと言うことができる。 PCP(r(·), q(·)) は、確率的検査可能証明のある言語のクラスであり、検証者は r(n) 回のコイントスと q(n) 回の神託機械への問い合わせが可能である（n は入力長）。