{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:38:36Z","timestamp":1780382316487,"version":"3.54.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1994,5,1]],"date-time":"1994-05-01T00:00:00Z","timestamp":767750400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1994,5]]},"DOI":"10.1007\/bf01178668","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T19:40:37Z","timestamp":1108669237000},"page":"479-502","source":"Crossref","is-referenced-by-count":7,"title":["On problems with short certificates"],"prefix":"10.1007","volume":"31","author":[{"given":"Graham","family":"Farr","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proc. 3rd Ann. ACM Symp. on Theory of Comput., Assoc. Comput. Mach., New York, 1971, pp. 151?158","DOI":"10.1145\/800157.805047"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"Davis, M., Putnam, H.: A computing procedure for quantificational theory. J. Assoc. Comput. Mach.7, 201?215 (1960)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF02090764","volume":"23","author":"J. D\u00edaz","year":"1990","unstructured":"D\u00edaz, J., Tor\u00e1n, J.: Classes of bounded nondeterminism. Math. Syst. Theory23, 21?32 (1990)","journal-title":"Math. Syst. Theory"},{"key":"CR4","unstructured":"Farr, G.E.: Topics in computational complexity. D. Phil. Thesis, University of Oxford, 1986"},{"key":"CR5","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. San Francisco: WH Freeman 1979"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci.1, 237?267 (1976)","journal-title":"Theoret. Comput. Sci."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J Comput.5, 704?714 (1976)","journal-title":"SIAM J Comput."},{"key":"CR8","volume-title":"Ramsey theory","author":"R.L. Graham","year":"1980","unstructured":"Graham, R.L., Rothschild, B.L., Spencer, J.H.: Ramsey theory. New York: Wiley 1980"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N.D. Jones","year":"1977","unstructured":"Jones, N.D., Laaser, W.T.: Complete problems for deterministic polynomial time. Theoret. Comput. Sci.3, 105?117 (1977)","journal-title":"Theoret. Comput. Sci."},{"key":"CR10","unstructured":"Kintala, C.M.R., Fischer, P.C.: Computations with a restricted number of nondeterministic steps. In: Proc. 9th Ann. ACM Symp. on Theory of Comput., Assoc. Comput. Mach., New York, 1977, pp. 178?185"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/0209003","volume":"9","author":"C.M.R. Kintala","year":"1980","unstructured":"Kintala, C.M.R., Fischer, P.C.: Refining nondeterminism in relativized polynomial-time bounded computations. SIAM J. Comput.9, 46?53 (1980)","journal-title":"SIAM J. Comput."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of polynomial time reducibility. J. Assoc. Comput. Mach.22, 155?171 (1975)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR13","first-page":"239","volume":"25","author":"B. Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. Ann. Discrete Math.25, 239?254 (1985)","journal-title":"Ann. Discrete Math."},{"key":"CR14","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/3-540-10291-4_20","volume-title":"Proc. 6th Internat. Workshop, Bad Honnef, 1980","author":"B. Monien","year":"1981","unstructured":"Monien, B., Sudborough, I.H.: Bounding the bandwidth of NP-complete problems. In: Graph-theoretic concepts in computer science. Proc. 6th Internat. Workshop, Bad Honnef, 1980. (Lect. Notes Comput. Sci., vol. 100, pp. 279?292) Berlin, Heidelberg, New York: Springer 1981"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(85)90068-4","volume":"41","author":"B. Monien","year":"1985","unstructured":"Monien, B., Sudborough, I.H.: Bandwidth constrained NP-complete problems. Theoret. Comput. Sci.41, 141?167 (1985)","journal-title":"Theoret. Comput. Sci."},{"key":"CR16","volume-title":"Combinatorial optimization: algorithms and complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Englewood Cliffs, NJ: Prentice-Hall 1982"},{"key":"CR17","volume-title":"Theory of recursive functions and effective computability","author":"H. Rogers","year":"1967","unstructured":"Rogers, H.: Theory of recursive functions and effective computability. New York: McGraw-Hill 1967"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01178668.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01178668\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01178668","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T13:07:54Z","timestamp":1556629674000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01178668"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,5]]},"references-count":17,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1994,5]]}},"alternative-id":["BF01178668"],"URL":"https:\/\/doi.org\/10.1007\/bf01178668","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,5]]}}}