Complexity of the search for a Challenge-Response reduction

Peter Vojtáš

Abstract

The idea of reducing (translating) a challenge (question) to another, with the aim of using response (solution, answer) to the latter to obtain response to the former, is a basic and natural one in all areas of human endeavor. We call such a back and forth procedure here "Challenge-Response Reduction (CRR)". We address particular aspects of CRR in complexity reduction.