Some independence results in complexity theory^†

^†This research was supported in part by NSF Grants MCS8102853 and MCS8304756.

Abstract

We give a formal definition of a property which informally says that problem B is independent of problem A if the existence of an “oracle” which solves problem A at zero cost does not help to reduce the cost of any algorithm which solves problem B. We then show, for example, that matrix multiplication is independent of any of the following problems: computing the transitive closure of a graph, the rank of a matrix, a set of independent rows and columns in a matrix, a maximum bipartite matching, etc.

Keywords:

• Complexity Theory
• Algebraic Function
• Straight-Line Program
• Matrix Multiplication
• Oracle

C.R. Categories:

• F.2.1
• F.2.2
• F.2.3

^†This research was supported in part by NSF Grants MCS8102853 and MCS8304756.

^†This research was supported in part by NSF Grants MCS8102853 and MCS8304756.

Notes

^†This research was supported in part by NSF Grants MCS8102853 and MCS8304756.