[Model] FaultDetectionInLogicCircuits

[isPANN]

Motivation

FAULT DETECTION IN LOGIC CIRCUITS (MS17) from Garey & Johnson, A1.2. Given a combinational logic circuit (a DAG of AND/OR/NOT gates) and a subset V' of vertices (lines), determine whether all single stuck-at faults on lines in V' can be detected by some input test pattern. NP-complete even if V' = V (all lines) or V' consists of a single input vertex (Ibarra and Sahni 1975). Applications in VLSI testing, design-for-testability, and automatic test pattern generation (ATPG).

Associated rules:

• [Rule] 3-Satisfiability to Fault Detection in Logic Circuits #919: 3-Satisfiability → FaultDetectionInLogicCircuits (NP-completeness proof from Garey & Johnson / Ibarra & Sahni 1975)

Definition

Name: FaultDetectionInLogicCircuits
Reference: Garey & Johnson, Computers and Intractability, A1.2 MS17; Ibarra and Sahni 1975

Mathematical definition:

INSTANCE: A combinational logic circuit C (a directed acyclic graph where vertices represent gates — AND, OR, NOT — and edges represent signal lines), a subset V' ⊆ V of vertices (lines).
QUESTION: Can all single stuck-at faults (stuck-at-0 and stuck-at-1) on lines in V' be detected? A fault is detectable if there exists an input pattern such that the output of the faulty circuit differs from the output of the fault-free circuit.

Variables

• Count: n_inputs (number of primary inputs)
• Per-variable domain: {0, 1}
• Meaning: Each variable represents a primary input value. The problem asks whether for every fault site v in V' and every stuck-at type (0 and 1), there exists an input assignment that detects the fault (produces a different primary output than the fault-free circuit). This is a feasibility problem with Value = Or.

Schema (data type)

Type name: FaultDetectionInLogicCircuits
Variants: none (unique input structure)

Field	Type	Description
num_inputs	usize	Number of primary input vertices
gates	Vec<Gate>	List of gates, each with type (AND/OR/NOT) and input wire indices
outputs	Vec<usize>	Indices of primary output gates
fault_vertices	Vec<usize>	Subset V' of vertices where faults must be detectable

where Gate has fields: gate_type: GateType (enum AND/OR/NOT), inputs: Vec<usize> (indices of input wires).

Notes:

• Indexing convention: primary inputs are indexed 0..num_inputs, gates are indexed num_inputs..num_inputs + gates.len().
• Key getter methods: num_inputs() (= number of primary inputs), num_gates() (= gates.len()), num_fault_vertices() (= fault_vertices.len()).
• dims() = vec![2; num_inputs] — one binary variable per primary input.

Complexity

• Decision complexity: NP-complete (Ibarra and Sahni, 1975; transformation from 3-Satisfiability per Garey & Johnson). NP-complete even if V' = V or V' = {single input vertex}.
• Best known exact algorithm: O*(2^n_inputs) by enumerating all input patterns and checking detectability of each fault. In practice, ATPG tools use structural heuristics (D-algorithm, PODEM, FAN) that are efficient for most practical circuits but worst-case exponential.
• Concrete complexity expression: "2^num_inputs" (for declare_variants!)
• References:
  • O. H. Ibarra and S. Sahni (1975). "Polynomially complete fault detection problems." IEEE Transactions on Computers C-24(3), pp. 242-249.

Extra Remark

Full book text:

INSTANCE: Logic circuit C (a dag of AND, OR, NOT gates), subset V' ⊆ V of vertices of C.
QUESTION: Can all "single stuck-at faults" on lines corresponding to members of V' be "detected"?

Reference: [Ibarra and Sahni, 1975]. Transformation from 3-SATISFIABILITY.
Comment: NP-complete even if V' = V or V' is a single input vertex.

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming.
• Other:

Note: Bruteforce: for each fault site v in V' and each fault type (stuck-at-0, stuck-at-1), enumerate all 2^n_inputs input patterns to find one that produces different output. If any fault is undetectable (no input distinguishes it), answer NO. This is O(|V'| * 2^n_inputs * circuit_size).

Example Instance

Positive instance (YES):

Circuit encoding the 3SAT formula (x₀ ∨ ¬x₁ ∨ x₂) ∧ (¬x₀ ∨ x₁ ∨ ¬x₂):

• 3 primary inputs: x₀ (idx 0), x₁ (idx 1), x₂ (idx 2)
• Gate g₀ (idx 3) = NOT x₁
• Gate g₁ (idx 4) = NOT x₀
• Gate g₂ (idx 5) = NOT x₂
• Gate g₃ (idx 6) = OR(x₀, g₀, x₂) — clause C₁
• Gate g₄ (idx 7) = OR(g₁, x₁, g₂) — clause C₂
• Gate g₅ (idx 8) = AND(g₃, g₄) — output
• Outputs: [8]
• V' = {8} (stuck-at-0 on the output gate)

The formula is satisfiable (e.g., x₀=1, x₁=1, x₂=0), so the circuit output can be 1, meaning stuck-at-0 on the output is detectable. Stuck-at-1 is also detectable (any input making the output 0 detects it, e.g., x₀=0, x₁=0, x₂=0 gives C₁ = 0 ∨ 1 ∨ 0 = 1, C₂ = 1 ∨ 0 ∨ 1 = 1 → output 1; but x₀=0, x₁=1, x₂=1 gives C₁ = 0 ∨ 0 ∨ 1 = 1, C₂ = 1 ∨ 1 ∨ 0 = 1 → output 1. Actually trying x₀=0, x₁=0, x₂=1: C₁ = 0 ∨ 1 ∨ 1 = 1, C₂ = 1 ∨ 0 ∨ 0 = 1 → output 1. The formula is a tautology-like formula. Let's check x₀=1, x₁=0, x₂=1: C₁ = 1 ∨ 1 ∨ 1 = 1, C₂ = 0 ∨ 0 ∨ 0 = 0 → output 0. So input (1,0,1) makes the output 0, detecting stuck-at-1.)

Expected Outcome: YES — all stuck-at faults on V' = {8} are detectable.

• Stuck-at-0 detected by input (1, 1, 0): fault-free output = 1, faulty output = 0.
• Stuck-at-1 detected by input (1, 0, 1): fault-free output = 0, faulty output = 1.

Negative instance (NO):

Circuit encoding (x₀) ∧ (¬x₀) — unsatisfiable:

• 1 primary input: x₀ (idx 0)
• Gate g₀ (idx 1) = NOT x₀
• Gate g₁ (idx 2) = AND(x₀, g₀) — output (always 0)
• Outputs: [2]
• V' = {2} (stuck-at-0 on the output gate)

The output is always 0 regardless of input. Stuck-at-0 on the output produces the same value (0) for every input, so it is undetectable.

Expected Outcome: NO — stuck-at-0 fault on line 2 is undetectable.

Python validation script

"""Validate FaultDetectionInLogicCircuits examples."""
from itertools import product

AND, OR, NOT = "AND", "OR", "NOT"

def check_fault_detection(num_inputs, gates, outputs, fault_vertices):
    """Check if all single stuck-at faults on fault_vertices are detectable."""
    all_inputs = list(product([0, 1], repeat=num_inputs))

    for fv in fault_vertices:
        for stuck_val in [0, 1]:
            detected = False
            for inp in all_inputs:
                # Fault-free evaluation
                ff = list(inp)
                for gt, gi in gates:
                    r = [ff[i] for i in gi]
                    if gt == NOT: ff.append(1 - r[0])
                    elif gt == AND: ff.append(1 if all(r) else 0)
                    elif gt == OR: ff.append(1 if any(r) else 0)
                ff_out = tuple(ff[o] for o in outputs)

                # Faulty evaluation
                if fv < num_inputs:
                    fa = list(inp); fa[fv] = stuck_val
                    for gt, gi in gates:
                        r = [fa[i] for i in gi]
                        if gt == NOT: fa.append(1 - r[0])
                        elif gt == AND: fa.append(1 if all(r) else 0)
                        elif gt == OR: fa.append(1 if any(r) else 0)
                else:
                    fa = list(inp)
                    for idx, (gt, gi) in enumerate(gates):
                        r = [stuck_val if i == fv else fa[i] for i in gi]
                        line = num_inputs + idx
                        if line == fv:
                            fa.append(stuck_val)
                        elif gt == NOT: fa.append(1 - r[0])
                        elif gt == AND: fa.append(1 if all(r) else 0)
                        elif gt == OR: fa.append(1 if any(r) else 0)
                fa_out = tuple(fa[o] for o in outputs)

                if ff_out != fa_out:
                    detected = True
                    break
            if not detected:
                return False, fv, stuck_val
    return True, None, None

# Example 1: Positive (YES)
# (x0 OR NOT x1 OR x2) AND (NOT x0 OR x1 OR NOT x2)
gates1 = [
    (NOT, [1]),       # idx 3: NOT x1
    (NOT, [0]),       # idx 4: NOT x0
    (NOT, [2]),       # idx 5: NOT x2
    (OR, [0, 3, 2]),  # idx 6: clause C1
    (OR, [4, 1, 5]),  # idx 7: clause C2
    (AND, [6, 7]),    # idx 8: output
]
r1, _, _ = check_fault_detection(3, gates1, [8], [8])
assert r1, "Expected YES"
print(f"Example 1 (positive): {'YES' if r1 else 'NO'}")

# Example 2: Negative (NO)
# (x0) AND (NOT x0) — always 0
gates2 = [
    (NOT, [0]),       # idx 1: NOT x0
    (AND, [0, 1]),    # idx 2: output (always 0)
]
r2, fv, sv = check_fault_detection(1, gates2, [2], [2])
assert not r2, "Expected NO"
print(f"Example 2 (negative): {'YES' if r2 else 'NO'} (undetectable: line {fv}, stuck-at-{sv})")

print("All assertions passed!")

References

• [Ibarra and Sahni, 1975]: O. H. Ibarra and S. Sahni (1975). "Polynomially complete fault detection problems." IEEE Transactions on Computers C-24(3), pp. 242-249.
• [Garey and Johnson, 1979]: M. R. Garey and D. S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, pp. 227 (MS17).

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction to/from any existing problem — orphan node
Non-trivial	✅ Pass	Distinct feasibility problem not isomorphic to existing models
Correctness	⚠️ Warn	References verified but complexity bound is naive brute-force; reduction source discrepancy noted
Well-written	❌ Fail	Missing Expected Outcome section; example too simple; variable semantics unclear

Overall: 1 passed, 1 warning, 2 failed

---

Usefulness

The problem FaultDetectionInLogicCircuits does not exist in the codebase (pred show confirms). However, the issue does not mention any concrete reduction rule connecting this problem to the existing reduction graph. The "How to solve" section only checks brute-force and does not identify any reduction to/from an existing problem (e.g., CircuitSAT, Satisfiability, DNFNonTautology).

A problem without any planned reduction rule has no value in the reduction graph. Add at least one planned reduction to/from an existing problem — for example, the Ibarra & Sahni paper itself reduces from DNF Non-Tautology, which could serve as a natural connection point.

Non-trivial

This is a genuinely distinct problem. While the codebase has circuit-related problems (CircuitSAT), fault detection in logic circuits has fundamentally different feasibility constraints: rather than asking whether there exists a satisfying assignment, it asks whether every stuck-at fault on specified lines can be detected by some input pattern. The universal quantifier over faults combined with the existential quantifier over test patterns makes this structurally different from any existing model.

Correctness

References verified:

• Ibarra and Sahni (1975): Confirmed as "Polynomially Complete Fault Detection Problems," IEEE Transactions on Computers, C-24(3):242-249, March 1975. The paper exists and does prove NP-completeness of the fault detection problem.
• Garey & Johnson MS17: Consistent with the known G&J appendix entry.

Discrepancy noted: The issue quotes G&J as stating "Transformation from 3-SATISFIABILITY," but the actual Ibarra & Sahni paper reduces from DNF Non-Tautology, not 3-SAT. This is a known discrepancy in G&J (G&J listed 3-SAT for many logic-based problems). The issue should note this discrepancy rather than potentially misleading implementers.

Complexity: The complexity string "2^num_inputs" represents naive brute-force enumeration. This is technically correct as an upper bound but is not the "best known exact algorithm" — it is simply exhaustive search. For an NP-complete problem, there may be better exact algorithms (e.g., using structural properties of the circuit). However, no significantly better general-purpose exact algorithm is widely known for this problem, so this is acceptable as a conservative bound.

Well-written

Missing sections:

1. Expected Outcome: The template requires a concrete expected outcome for the example. For this feasibility problem, the issue should state the answer (YES/NO) and provide a concrete satisfying witness (the set of test patterns that detect all faults) with justification.

Variable semantics issues:
2. The "Variables" section describes n_inputs primary input values with domain {0,1}. However, the problem is a decision problem (can ALL faults be detected?), not an optimization problem. The variable mapping is unclear — is each variable one primary input? But detecting different faults may require different input patterns, so the search space is more nuanced than a single binary assignment. The issue should clarify: is the search space over individual input patterns (one per fault), or over sets of test patterns?

Example quality issues:
3. The example (2 inputs, 1 AND gate, V'={x1}) is too simple for meaningful round-trip testing. With only 2 inputs (4 possible patterns) and 1 fault site (2 faults), it is trivially solvable and would pass even with a buggy implementation. The example should have at least 3-4 inputs, multiple gates, and a V' with multiple vertices — ideally including at least one undetectable fault to exercise the NO case as well.
4. The second "example" (NOT -> self-AND) is a hand-wave sketch, not a fully worked instance. It should either be removed or fully specified with concrete gate indices and fault analysis.

Other issues:
5. The schema proposes gates: Vec<Gate> with inputs: Vec<usize> for gate inputs, but does not clarify the indexing convention — are primary inputs indexed 0..num_inputs and gates indexed num_inputs..num_inputs+gates.len()? This needs to be explicit for implementability.
6. The issue does not specify whether this is a witness-capable feasibility problem (Value = Or, where the witness is a set of test patterns) or an aggregate-only problem. This affects implementation.

Recommendations

• Add a planned reduction, e.g., DNFNonTautology -> FaultDetectionInLogicCircuits (following Ibarra & Sahni's original proof direction), or a reduction to/from CircuitSAT or Satisfiability.
• Provide a richer example with 3+ inputs, multiple gate types, and ideally two sub-examples: one with answer YES and one with answer NO (undetectable fault due to redundant logic).
• Clarify the variable semantics: the problem likely needs Value = Or (feasibility) where the "witness" is a mapping from fault sites to detecting input patterns.
• Note the G&J vs. Ibarra & Sahni discrepancy on the reduction source (3-SAT vs. DNF Non-Tautology).

[isPANN]

Changelog (fix-issue)

Fixes applied based on check-issue report:

1. Usefulness (was: Fail): Added "Associated rules" section linking [Rule] 3-Satisfiability to Fault Detection in Logic Circuits #919 (3-Satisfiability → FaultDetectionInLogicCircuits), resolving orphan-node concern.
2. Well-written (was: Fail):
   • Added Expected Outcome for both positive and negative examples with concrete fault detection witnesses.
   • Replaced trivial 2-input example with a richer 3-input, 6-gate circuit encoding a 2-clause 3SAT formula, plus a negative instance (unsatisfiable formula → undetectable fault).
   • Clarified variable semantics: universal quantifier over faults × existential quantifier over inputs; Value = Or feasibility problem.
   • Added indexing convention to Schema notes (inputs 0..num_inputs, gates num_inputs..).
   • Added getter methods (num_inputs(), num_gates(), num_fault_vertices()) and dims() specification to Schema notes.
   • Added Python validation script in collapsible section.
3. Complexity: Added concrete complexity expression "2^num_inputs" for declare_variants! with Ibarra & Sahni reference.
4. Correctness (was: Warn): No change needed — the G&J text itself says "Transformation from 3-SATISFIABILITY" which matches [Rule] 3-Satisfiability to Fault Detection in Logic Circuits #919's reduction direction.