Lower bounds for some decision problems over C

DOI10.1016/S0304-3975(01)00273-0zbMATH Open1002.68162arXivmath/9904129WikidataQ127778762 ScholiaQ127778762MaRDI QIDQ1605321FDOQ1605321

Authors: Gregorio Malajovich 

Publication date: 15 July 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Lower bounds for some explicit decision problems over the complex numbers are given.

Full work available at URL: https://arxiv.org/abs/math/9904129

Recommendations

• Lower bounds for linear decision lists
• scientific article; zbMATH DE number 1351079
• Publication:4886070
• scientific article; zbMATH DE number 4087011
• Lower bounds for covering problems
• Lowering Undecidability Bounds for Decision Questions in Matrices
• Decidability results for the boundedness problem
• Lower Bounds on Minimal Weight of Partial Reducts and Partial Decision Rules
• A lower bound on determinantal complexity
• scientific article; zbMATH DE number 7711586

zbMATH Keywords

decision problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites Work

• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomials with Rational Coefficients Which are Hard to Compute
• On lower bounds for the complexity of polynomials and their multiples
• Title not available (Why is that?)

Cited In (2)

• Lower bounds and recursive methods for the problem of adjudicating conflicting claims
• Test complexity of generic polynomials

This page was built for publication: Lower bounds for some decision problems over \(C\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1605321)