論理関数の内包関数と外包関数について

書誌事項

タイトル別名
  • Interior and Exterior Functions of Boolean Functions

この論文をさがす

説明

本論文では,論理関数fの安定性を考察するためにfの内包関数,外包関数,および,層を定義し,この定義に関連したINTERIOR,EXTERIOR,LAYERの3つの問題を考えます.まず,fを正関数に限定しても,問題LAYERが,NP困難であること,および,P≠NPならば,問題INTERIORとEXTERIORに対する多項式時間アルゴリズムが存在しないことを示しました.しかしながら,2単調正関数においては,問題LAYERが多項式時間で解くことができること,さらに,問題INTERIORとEXTERIORに対する逐次多項式アルゴリズムの存在を示しました.
We define the interior functions,exterior functions and layers of a Boolean function f in order to investigate its stability,and consider three problems INTERIOR,EXTERIOR and LAYER associated with such definitions.We show that even if f is restricted to be a positive function,LAYER is NP-hard and there is no polynomial total time algorithm,unless P=NP,for INTERIOR and EXTERIOR.However, for a 2-monotonic positive function f,LAYER can be solved in polynomial time and there exist incrementally polynomial algorithms for INTERIOR and EXTERIOR.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1573387452166654208
  • NII論文ID
    110003191725
  • NII書誌ID
    AN10013152
  • 本文言語コード
    en
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ