{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T09:49:42Z","timestamp":1674121782453},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1995,9,1]],"date-time":"1995-09-01T00:00:00Z","timestamp":809913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Reliable Comput"],"published-print":{"date-parts":[[1995,9]]},"DOI":"10.1007\/bf02385263","type":"journal-article","created":{"date-parts":[[2006,4,9]],"date-time":"2006-04-09T11:07:40Z","timestamp":1144580860000},"page":"343-359","source":"Crossref","is-referenced-by-count":6,"title":["A bright side of NP-hardness of interval computations: interval heuristics applied to NP-problems"],"prefix":"10.1007","volume":"1","author":[{"given":"Bonnie","family":"Traylor","sequence":"first","affiliation":[]},{"given":"Vladik","family":"Kreinovich","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02385263_CR1","volume-title":"Life the Universe and everything","author":"D. Adams","year":"1983","unstructured":"Adams, D.Life the Universe and everything. Pocket Books, N.Y., 1983."},{"key":"BF02385263_CR2","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(91)90315-S","volume":"81","author":"O. Dubois","year":"1991","unstructured":"Dubois, O.,Counting the number of solutions for instances of satisfiability. Theoretical Computer Science81 (1991), pp. 49\u201364.","journal-title":"Theoretical Computer Science"},{"key":"BF02385263_CR3","unstructured":"Gaganov, A. A.Computational complexity of the range of the polynomial in several variables. Cybernetics (1985), pp. 418\u2013421."},{"key":"BF02385263_CR4","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M. and Johnson, D.Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco, 1979."},{"key":"BF02385263_CR5","unstructured":"Hansen, E. R.On solving systems of equations using interval arithmetic. Math. Comp. (1968), pp. 374\u2013384."},{"key":"BF02385263_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/3-540-16437-5_7","volume-title":"Interval Mathematics 1985","author":"H. Kolacz","year":"1986","unstructured":"Kolacz, H.On the optimality of inclusion algorithms. In: Nickel, K. (ed.) \u201cInterval Mathematics 1985\u201d, Lecture Notes in Computer Science 212, Springer-Verlag, Berlin, Heidelberg, N.Y., 1986, pp. 67\u201379."},{"key":"BF02385263_CR7","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(92)90029-U","volume":"43","author":"E. Koutsoupias","year":"1992","unstructured":"Koutsoupias, E. and Papadimitriou, C. H.On the greedy algorithm for satisfiability. Information Processing Letters43 (1992), pp. 53\u201355.","journal-title":"Information Processing Letters"},{"key":"BF02385263_CR8","unstructured":"Kreinovich, V.Maslov's increasing freedom of choice strategy: on the example of the satisfiability problem. Leningrad Center for New Informational Technology \u201cInformatika\u201d, Technical Report, 1989 (in Russian)."},{"key":"BF02385263_CR9","first-page":"31","volume":"2","author":"V. Kreinovich","year":"1991","unstructured":"Kreinovich, V., Bernat, A., Villa, E., and Mariscal, Y.Parallel computers estimate errors caused by imprecise data. Interval Computations, 2 (1991), pp. 31\u201346.","journal-title":"Interval Computations"},{"key":"BF02385263_CR10","first-page":"6","volume":"1","author":"V. Kreinovich","year":"1993","unstructured":"Kreinovich, V., Lakeyev, A. V., and Noskov, S. I.Optimal solution of interval linear systems is intractable (NP-hard), Interval Computations 1 (1993), pp. 6\u201314.","journal-title":"Interval Computations"},{"key":"BF02385263_CR11","first-page":"518","volume":"47","author":"A. V. Lakeyev","year":"1993","unstructured":"Lakeyev, A. V. and Noskov, S. I.A description of the set of solutions of a linear equation with interval defined operator and right-hand side. Russian Acad. Sci. Dokl. Math.47 (1993), pp.518\u2013523.","journal-title":"Russian Acad. Sci. Dokl. Math."},{"key":"BF02385263_CR12","unstructured":"Maslov, S. Yu. and Kurenkov, Yu. N.The increasing freedom of choice strategy for the satisfiability problem. In: \u201cProceedings of the USSR National Conference on Methods of Mathematical Logic in Artificial Intelligence and Programming\u201d, Palanga, 1980 (in Russian)."},{"key":"BF02385263_CR13","volume-title":"Theory of deductive systems and its applications","author":"S. Yu. Maslov","year":"1987","unstructured":"Maslov, S. Yu.Theory of deductive systems and its applications. MIT Press, Cambridge, MA, 1987."},{"key":"BF02385263_CR14","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970906","volume-title":"Methods and applications of interval analysis","author":"R. E. Moore","year":"1979","unstructured":"Moore, R. E.Methods and applications of interval analysis. SIAM, Philadelphia, 1979."},{"key":"BF02385263_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01213466","volume":"6","author":"S. Poljak","year":"1993","unstructured":"Poljak, S. and Rohn, J.Checking robust non-singularity is NP-hard. Mathematics of Control, Signals, and Systems6 (1993), pp. 1\u20139.","journal-title":"Mathematics of Control, Signals, and Systems"},{"key":"BF02385263_CR16","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/B978-0-12-518850-0.50041-X","volume-title":"Interval Mathematics 1980","author":"L. B. Rall","year":"1980","unstructured":"Rall, L. B.Optimization of interval computations. In: Nickel, K. (ed.) \u201cInterval Mathematics 1980\u201d Academic Press, N.Y., 1980, pp. 489\u2013498."},{"key":"BF02385263_CR17","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1016\/B978-0-12-518850-0.50042-1","volume-title":"Interval Mathematics 1980","author":"H. Ratschek","year":"1980","unstructured":"Ratschek, H. and Rokne, J.Optimality of the centered form. In: Nickel, K. (ed.) \u201cInterval Mathematics 1980\u201d, Academic Press, N.Y., 1980, pp. 499\u2013508."},{"issue":"2","key":"BF02385263_CR18","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1137\/S0895479893251198","volume":"16","author":"J. Rohn","year":"1994","unstructured":"Rohn, J. and Kreinovich, V.Computing exact componentwise bounds on solutions of linear systems with interval data is NP-hard. SIAM Journal on Matrix Analysis and Applications (SIMAX)16(2) (1994), pp. 415\u2013420.","journal-title":"SIAM Journal on Matrix Analysis and Applications (SIMAX)"}],"container-title":["Reliable Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02385263.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02385263\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02385263","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T07:40:07Z","timestamp":1558078807000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02385263"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["BF02385263"],"URL":"https:\/\/doi.org\/10.1007\/bf02385263","relation":{},"ISSN":["1385-3139","1573-1340"],"issn-type":[{"value":"1385-3139","type":"print"},{"value":"1573-1340","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}