Affiliations: Department of Combinatorics and Optimization, University of Waterloo, ON, N2L 3G1, Canada. ygwang@cacr.math.uwaterloo.ca | Department of Computer Science, Florida State University, Tallahassee, FL 32306-4530, USA. desmedt@cs.fsu.edu | Information Security Group, Royal Holloway – University of London | Information Security Group, Royal Holloway – University of London, Egham, Surrey TW20 OEX, UK. m.burmester@rhbnc.ac.uk
Note: [] Address for correspondence: Department of Combinatorics and Optimization, University of Waterloo, ON, N2L 3G1, Canada
Note: [] Address for correspondence: Information Security Group, Royal Holloway – University of London
Note: [] Address for correspondence: Information Security Group, Royal Holloway – University of London
Abstract: We consider the problem of dependable computation with multiple inputs. The goal is to study when redundancy can help to achieve survivability and when it cannot. We use AND/OR graphs to model fault tolerant computations with multiple inputs. While there is a polynomial time algorithm for finding vertex disjoint paths in networks, we will show that the equivalent problem in computation systems with multiple inputs is NP-hard. Our main results are as follows. (1) We present a general model for fault tolerant computation systems with multiple inputs: AND/OR graphs. (2) We show that it is NP-hard to find two vertex disjoint solution graphs in an AND/OR graph. It follows that in the general case redundancy cannot help to achieve survivability, assuming P≠NP.
