{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:30:23Z","timestamp":1757626223071,"version":"3.44.0"},"reference-count":44,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[1996,9,1]],"date-time":"1996-09-01T00:00:00Z","timestamp":841536000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1996,9,1]],"date-time":"1996-09-01T00:00:00Z","timestamp":841536000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[1999,2,20]],"date-time":"1999-02-20T00:00:00Z","timestamp":919468800000},"content-version":"vor","delay-in-days":902,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Annals of Pure and Applied Logic"],"published-print":{"date-parts":[[1996,9]]},"DOI":"10.1016\/0168-0072(95)00051-8","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T00:29:52Z","timestamp":1027643392000},"page":"125-170","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the lattices of NP-subspaces of a polynomial time vector space over a finite field"],"prefix":"10.1016","volume":"81","author":[{"given":"Anil","family":"Nerode","sequence":"first","affiliation":[]},{"given":"J.B","family":"Remmel","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0168-0072(95)00051-8_BIB1","series-title":"Structural Complexity I","article-title":"Structural Complexity I","author":"Balc\u00e1zar","year":"1988"},{"key":"10.1016\/0168-0072(95)00051-8_BIB2","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","article-title":"Relativisations of the P = NP question","volume":"4","author":"Baker","year":"1981","journal-title":"SIAM J. Comp."},{"key":"10.1016\/0168-0072(95)00051-8_BIB3","unstructured":"F.A. B\u00e4uerle, Ph.D. Thesis, University of California at San Diego, La Jolla, CA 92093."},{"key":"10.1016\/0168-0072(95)00051-8_BIB4","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","article-title":"Relative to a random oracle A, PA \u2260 NPA \u2260 Co-NPA with probability 1","volume":"10","author":"Bennett","year":"1981","journal-title":"SIAM J. Comp."},{"key":"10.1016\/0168-0072(95)00051-8_BIB5","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0022-0000(78)90034-X","article-title":"On splitting recursive sets","volume":"17","author":"Breidbart","year":"1978","journal-title":"J. Comput. System Sci."},{"article-title":"On some most probable separations of complexity classes","year":"1986","author":"Jin-yi","key":"10.1016\/0168-0072(95)00051-8_BIB6"},{"key":"10.1016\/0168-0072(95)00051-8_BIB7","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0168-0072(91)90008-A","article-title":"Polynomial-time versus recursive models","volume":"54","author":"Cenzer","year":"1991","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/0168-0072(95)00051-8_BIB8","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0168-0072(92)90076-C","article-title":"Polynomial-time Abelian groups","volume":"56","author":"Cenzer","year":"1982","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/0168-0072(95)00051-8_BIB9","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0165-4896(92)90059-E","article-title":"Recursively presented games and strategies","volume":"24","author":"Cenzer","year":"1992","journal-title":"Math. Social Sci."},{"key":"10.1016\/0168-0072(95)00051-8_BIB10","series-title":"Feasible Mathematics II","first-page":"91","article-title":"Feasibly categorical Abelian groups","volume":"Vol. 13","author":"Cenzer","year":"1995"},{"key":"10.1016\/0168-0072(95)00051-8_BIB11","unstructured":"D. Cenzer and J.B. Remmel, Feasible graphs and colorings, Math. Logic Quart., to appear."},{"key":"10.1016\/0168-0072(95)00051-8_BIB12","unstructured":"D. Cenzer and J.B. Remmel, Feasibly categorical models, Lecture Notes in Computer Science, to appear."},{"key":"10.1016\/0168-0072(95)00051-8_BIB13","series-title":"Proc. Internat. Cong. for Logic Methodology, and Philosophy of Science","first-page":"24","article-title":"The intrinsic computational difficulty of functions","author":"Cobham","year":"1964"},{"key":"10.1016\/0168-0072(95)00051-8_BIB14","series-title":"ACM Symp. on Theory of Computation","first-page":"151","article-title":"The complexity of theorem-proving procedures","author":"Cook","year":"1971"},{"key":"10.1016\/0168-0072(95)00051-8_BIB15","series-title":"Upside Down A Book Company","article-title":"Aspects of effective algebra","author":"Crossley","year":"1981"},{"key":"10.1016\/0168-0072(95)00051-8_BIB16","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1305\/ndjfl\/1093894296","article-title":"Two notes on vector spaces with recursive operations","volume":"12","author":"Dekker","year":"1971","journal-title":"Notre Dame J. Formal Logic"},{"key":"10.1016\/0168-0072(95)00051-8_BIB17","series-title":"Complexity Theory","first-page":"166","article-title":"Fixed parameter intractability and completeness III: some structural aspects of the W-Heirarchy","author":"Downey","year":"1993"},{"key":"10.1016\/0168-0072(95)00051-8_BIB18","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees, and flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Canad. J. Math"},{"year":"1979","series-title":"Computers and Intractability","author":"Garey","key":"10.1016\/0168-0072(95)00051-8_BIB19"},{"key":"10.1016\/0168-0072(95)00051-8_BIB20","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","article-title":"On the computational complexity of algorithms","volume":"117","author":"Hartmanis","year":"1965","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0168-0072(95)00051-8_BIB21","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0304-3975(83)90003-8","article-title":"Oracel dependent properties of the lattice NP-sets","volume":"24","author":"Homer","year":"1983","journal-title":"Theoret. Comput. Sci."},{"year":"1969","series-title":"Formal languages and their relations to automata","author":"Hopcroft","key":"10.1016\/0168-0072(95)00051-8_BIB22"},{"key":"10.1016\/0168-0072(95)00051-8_BIB23","doi-asserted-by":"crossref","first-page":"481","DOI":"10.2307\/2271869","article-title":"Maximal vector spaces under automorphisms of the lattice of recursively enumerable vector spaces","volume":"42","author":"Kalantari","year":"1977","journal-title":"J. Symbol. Logic"},{"key":"10.1016\/0168-0072(95)00051-8_BIB24","series-title":"Complexity Computer Computations","first-page":"85","article-title":"Reducibilities among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/0168-0072(95)00051-8_BIB25","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1002\/malq.19660120125","article-title":"Classes of recursively enumerable sets and degrees of unsolvability","volume":"12","author":"Martin","year":"1966","journal-title":"Zeit. Math. Logik"},{"key":"10.1016\/0168-0072(95)00051-8_BIB26","first-page":"209","article-title":"Recursion theory and algebra","volume":"450","author":"Metakides","year":"1975"},{"key":"10.1016\/0168-0072(95)00051-8_BIB27","first-page":"141","article-title":"Recursively enumerable vector spaces","volume":"11","author":"Metakides","year":"1979","journal-title":"Ann. Math. Logic"},{"key":"10.1016\/0168-0072(95)00051-8_BIB28","first-page":"323","article-title":"A survey of R.E. substructures","volume":"42","author":"Nerode","year":"1985"},{"key":"10.1016\/0168-0072(95)00051-8_BIB29","series-title":"Logic and Computer Science, Rendconti del Seminario Matematico: Covegno su Logic and Computer Science, New Trends and Applications (1986)","article-title":"Complexity theoretic algebra I: vector spaces over finite fields","author":"Nerode","year":"1987"},{"key":"10.1016\/0168-0072(95)00051-8_BIB30","series-title":"Proc. Structures in Complexity, Second Annual Conf.","first-page":"218","article-title":"Complexity theoretic algebra I: vector spaces over finite fields, extended abstract with proofs","author":"Nerode","year":"1987"},{"key":"10.1016\/0168-0072(95)00051-8_BIB31","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0168-0072(89)90047-X","article-title":"Complexity theoretic algebra II: Boolean algebras","volume":"44","author":"Nerode","year":"1989","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/0168-0072(95)00051-8_BIB32","series-title":"Proc. Logic in Computer Science (LICS)","first-page":"375","article-title":"Polynomial graded logic: a graded version of Godel's system T, extended abstract with proofs","author":"Nerode","year":"1989"},{"key":"10.1016\/0168-0072(95)00051-8_BIB33","series-title":"Logic and Computation: Proc. Workshop held at CMU","article-title":"Polynomial time equivalence types","volume":"Vol. 106","author":"Nerode","year":"1990"},{"key":"10.1016\/0168-0072(95)00051-8_BIB34","series-title":"Recursion Theory Week: Proc. Conf. at Oberwohlfach","article-title":"Polynomially isolated sets","author":"Nerode","year":"1990"},{"key":"10.1016\/0168-0072(95)00051-8_BIB35","series-title":"Feasible Mathematics","article-title":"Complexity-theoretic algebra: bases of vector spaces","author":"Nerode","year":"1990"},{"key":"10.1016\/0168-0072(95)00051-8_BIB36","doi-asserted-by":"crossref","first-page":"400","DOI":"10.2307\/2272868","article-title":"Maximal and cohesive vector spaces","volume":"42","author":"Remmel","year":"1977","journal-title":"J. Symbol. Logic"},{"key":"10.1016\/0168-0072(95)00051-8_BIB37","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0003-4843(78)90027-X","article-title":"Recursively enumerable boolean algebras","volume":"14","author":"Remmel","year":"1978","journal-title":"Ann. Math. Logic"},{"key":"10.1016\/0168-0072(95)00051-8_BIB38","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0003-4843(80)90016-9","article-title":"Recursion theory on algebraic structures with an independent set","volume":"18","author":"Remmel","year":"1980","journal-title":"Ann. Math. Logic"},{"key":"10.1016\/0168-0072(95)00051-8_BIB39","doi-asserted-by":"crossref","first-page":"20","DOI":"10.2307\/2273351","article-title":"On recursively enumerable and co-recursively enumerable vector spaces with nonextendible bases","volume":"45","author":"Remmel","year":"1980","journal-title":"J. Symbol. Logic"},{"key":"10.1016\/0168-0072(95)00051-8_BIB40","series-title":"Logical Methods","first-page":"713","article-title":"Polynomial time categoricty and linear orderings","volume":"Vol. 12","author":"Remmel","year":"1993"},{"key":"10.1016\/0168-0072(95)00051-8_BIB41","article-title":"Complexity and Structure","volume":"Vol. 211","author":"Schoening","year":"1986"},{"key":"10.1016\/0168-0072(95)00051-8_BIB42","first-page":"417","article-title":"On the theory of PTIME degrees of recursive sets","volume":"40","author":"Shinoda","year":"1990","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0168-0072(95)00051-8_BIB43","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(92)90078-T","article-title":"The p-T-degrees of the recursive sets: lattice embeddings, extensions of embeddings and the two quantifier theory","volume":"97","author":"Shore","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0168-0072(95)00051-8_BIB44","series-title":"IEEE Symp. on Found. of Computer Science [FOCS]","first-page":"1","article-title":"Separating the polynomial-time hierarchy by oracles","author":"Yao","year":"1985"}],"container-title":["Annals of Pure and Applied Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0168007295000518?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0168007295000518?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:39:22Z","timestamp":1757453962000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0168007295000518"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":44,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1996,9]]}},"alternative-id":["0168007295000518"],"URL":"https:\/\/doi.org\/10.1016\/0168-0072(95)00051-8","relation":{},"ISSN":["0168-0072"],"issn-type":[{"type":"print","value":"0168-0072"}],"subject":[],"published":{"date-parts":[[1996,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On the lattices of NP-subspaces of a polynomial time vector space over a finite field","name":"articletitle","label":"Article Title"},{"value":"Annals of Pure and Applied Logic","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0168-0072(95)00051-8","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1996 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}