Some independence results in complexity theory†
From MaRDI portal
Publication:3751002
DOI10.1080/00207168508803454zbMath0611.68017MaRDI QIDQ3751002
Publication date: 1985
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207168508803454
oracle; rank of a matrix; matrix multiplication; algebraic function; straight-line program; transitive closure of a graph; maximum bipartite matching; set of independent rows and columns in a matrix
68Q25: Analysis of algorithms and problem complexity
Cites Work