Switch to: References

Add citations

You must login to add citations.
  1. P versus np and computability theoretic constructions in complexity theory over algebraic structures.Gunther Mainhardt - 2004 - Journal of Symbolic Logic 69 (1):39-64.
    We show that there is a structure of countably infinite signature with $P = N_{2}P$ and a structure of finite signature with $P = N_{1}P$ and $N_{1}P \neq N_{2}P$ . We give a further example of a structure of finite signature with $P \neq N_{1}P$ and $N_{1}P \neq N_{2}P$ . Together with a result from [10] this implies that for each possibility of P versus NP over structures there is an example of countably infinite signature. Then we show that for (...)
    Download  
     
    Export citation  
     
    Bookmark