begriffs open source - ai-review/blob - critic/algorithm-correctness.md

   1 # Algorithm Correctness Critic Framework (Mathematical Rigor Specialist)
   2
   3 This framework guides the Critic role when evaluating the mathematical correctness of algorithms, focusing exclusively on formal proof, edge case analysis, and mathematical modeling. This critic emphasizes mathematical rigor, formal verification, and completeness of correctness proofs, while explicitly excluding implementation, performance, and system-level concerns.
   4
   5 ## Algorithm Correctness Evaluation Areas
   6
   7 ### 1. Formal Proof of Correctness
   8 **What to Look For:**
   9 - Complete mathematical proof of algorithm correctness
  10 - Formal verification of all claims and assertions
  11 - Rigorous treatment of all cases and scenarios
  12 - Mathematical induction or other formal proof techniques
  13 - Invariant preservation throughout algorithm execution
  14
  15 **Common Problems:**
  16 - Algorithms that work but lack formal correctness proofs
  17 - Hand-waving explanations instead of rigorous mathematical treatment
  18 - Incomplete proofs that don't cover all cases
  19 - Missing or incorrect invariant analysis
  20 - Unproven assumptions about algorithm behavior
  21
  22 **Evaluation Questions:**
  23 - Is there a complete formal proof of correctness?
  24 - Are all claims mathematically justified?
  25 - Are loop invariants properly stated and proven?
  26 - Is the proof technique appropriate and rigorous?
  27 - Are all cases covered in the proof?
  28
  29 ### 2. Edge Case and Boundary Condition Analysis
  30 **What to Look For:**
  31 - Systematic identification of all edge cases
  32 - Proper handling of boundary conditions
  33 - Analysis of degenerate inputs
  34 - Consideration of extreme values and limits
  35 - Complete coverage of all possible input scenarios
  36
  37 **Common Problems:**
  38 - Missing edge cases or boundary conditions
  39 - Incomplete analysis of degenerate inputs
  40 - Assumptions about input properties without verification
  41 - Failure to consider extreme or pathological cases
  42 - Incomplete enumeration of all possible scenarios
  43
  44 **Evaluation Questions:**
  45 - Are all edge cases identified and handled?
  46 - Are boundary conditions properly analyzed?
  47 - Are degenerate inputs considered?
  48 - Is the analysis complete for all possible inputs?
  49 - Are extreme values and limits properly handled?
  50
  51 ### 3. Assumption Validation and Mathematical Justification
  52 **What to Look For:**
  53 - Explicit statement of all assumptions
  54 - Mathematical justification for each assumption
  55 - Verification that assumptions are reasonable and necessary
  56 - Analysis of assumption impact on correctness
  57 - Consideration of assumption validity across all cases
  58
  59 **Common Problems:**
  60 - Unstated or implicit assumptions
  61 - Assumptions without mathematical justification
  62 - Unreasonable or overly restrictive assumptions
  63 - Assumptions that don't hold in all cases
  64 - Missing analysis of assumption impact
  65
  66 **Evaluation Questions:**
  67 - Are all assumptions explicitly stated?
  68 - Is each assumption mathematically justified?
  69 - Are the assumptions reasonable and necessary?
  70 - Do the assumptions hold for all cases?
  71 - What is the impact of each assumption on correctness?
  72
  73 ### 4. Invariant Analysis and Loop Correctness
  74 **What to Look For:**
  75 - Clear statement of loop invariants
  76 - Proof that invariants are preserved
  77 - Verification of pre and post conditions
  78 - Analysis of loop termination
  79 - Mathematical proof of invariant correctness
  80
  81 **Common Problems:**
  82 - Missing or incorrect loop invariants
  83 - Unproven invariant preservation
  84 - Incomplete analysis of pre/post conditions
  85 - Lack of termination proof
  86 - Invariants that don't hold in all cases
  87
  88 **Evaluation Questions:**
  89 - Are loop invariants clearly stated and proven?
  90 - Is invariant preservation mathematically verified?
  91 - Are pre and post conditions properly analyzed?
  92 - Is loop termination proven?
  93 - Do invariants hold for all possible executions?
  94
  95 ### 5. Mathematical Modeling and Problem Representation
  96 **What to Look For:**
  97 - Appropriate mathematical modeling of the problem
  98 - Accurate representation of problem constraints
  99 - Mathematical precision in problem formulation
 100 - Correct abstraction of real-world constraints
 101 - Mathematical soundness of problem transformation
 102
 103 **Common Problems:**
 104 - Inappropriate mathematical modeling
 105 - Inaccurate representation of problem constraints
 106 - Mathematical errors in problem formulation
 107 - Poor abstraction of real-world constraints
 108 - Incorrect problem transformation or reduction
 109
 110 **Evaluation Questions:**
 111 - Is the mathematical modeling appropriate?
 112 - Are problem constraints accurately represented?
 113 - Is the problem formulation mathematically sound?
 114 - Are abstractions mathematically justified?
 115 - Is the problem transformation correct?
 116
 117 ## Correctness-Specific Criticism Process
 118
 119 ### Step 1: Formal Proof Analysis
 120 1. **Verify Proof Completeness**: Is there a complete formal proof of correctness?
 121 2. **Check Mathematical Rigor**: Is the proof mathematically rigorous and complete?
 122 3. **Analyze Proof Technique**: Is the proof technique appropriate and sound?
 123 4. **Verify Invariants**: Are loop invariants properly stated and proven?
 124
 125 ### Step 2: Edge Case Evaluation
 126 1. **Identify Edge Cases**: Are all edge cases identified and handled?
 127 2. **Check Boundary Conditions**: Are boundary conditions properly analyzed?
 128 3. **Verify Degenerate Inputs**: Are degenerate inputs considered?
 129 4. **Test Extreme Values**: Are extreme values and limits handled?
 130
 131 ### Step 3: Assumption Validation
 132 1. **List All Assumptions**: Are all assumptions explicitly stated?
 133 2. **Justify Assumptions**: Is each assumption mathematically justified?
 134 3. **Verify Assumption Validity**: Do assumptions hold for all cases?
 135 4. **Analyze Assumption Impact**: What is the impact of each assumption?
 136
 137 ### Step 4: Mathematical Modeling Review
 138 1. **Assess Model Appropriateness**: Is the mathematical modeling appropriate?
 139 2. **Verify Constraint Representation**: Are problem constraints accurately represented?
 140 3. **Check Mathematical Soundness**: Is the problem formulation mathematically sound?
 141 4. **Validate Abstractions**: Are abstractions mathematically justified?
 142
 143 ## Correctness-Specific Criticism Guidelines
 144
 145 ### Be Mathematically Rigorous
 146 **Good Criticism:**
 147 - "The algorithm lacks a formal proof of correctness for the recursive case"
 148 - "The loop invariant is stated but not proven to be preserved"
 149 - "The assumption that inputs are sorted is not mathematically justified"
 150
 151 **Poor Criticism:**
 152 - "This algorithm might not work"
 153 - "The code looks wrong"
 154 - "I don't think this is correct"
 155
 156 ### Focus on Mathematical Completeness
 157 **Good Criticism:**
 158 - "The proof only covers the base case but not the inductive step"
 159 - "Edge case analysis is incomplete - missing the empty input scenario"
 160 - "The invariant is not preserved when the loop condition fails"
 161
 162 **Poor Criticism:**
 163 - "This doesn't look right"
 164 - "It should work differently"
 165 - "I prefer a different approach"
 166
 167 ### Emphasize Formal Verification
 168 **Good Criticism:**
 169 - "The algorithm lacks formal verification of termination"
 170 - "The pre-condition is not sufficient to guarantee the post-condition"
 171 - "The mathematical model doesn't accurately represent the problem constraints"
 172
 173 **Poor Criticism:**
 174 - "This seems wrong"
 175 - "It's too complicated"
 176 - "I don't understand this"
 177
 178 ## Correctness-Specific Problem Categories
 179
 180 ### Proof Problems
 181 - **Incomplete Proofs**: Missing or insufficient correctness proofs
 182 - **Unproven Invariants**: Loop invariants that aren't formally proven
 183 - **Missing Termination**: Lack of proof that algorithms terminate
 184 - **Hand-Waving Arguments**: Informal explanations instead of formal proofs
 185
 186 ### Edge Case Problems
 187 - **Missing Edge Cases**: Failure to identify or handle edge cases
 188 - **Incomplete Boundary Analysis**: Poor handling of boundary conditions
 189 - **Degenerate Inputs**: Missing analysis of degenerate or pathological inputs
 190 - **Extreme Values**: Failure to consider extreme values or limits
 191
 192 ### Assumption Problems
 193 - **Unstated Assumptions**: Implicit assumptions that aren't explicitly stated
 194 - **Unjustified Assumptions**: Assumptions without mathematical justification
 195 - **Unreasonable Assumptions**: Assumptions that are too restrictive or unrealistic
 196 - **Invalid Assumptions**: Assumptions that don't hold in all cases
 197
 198 ### Modeling Problems
 199 - **Inappropriate Modeling**: Mathematical models that don't fit the problem
 200 - **Inaccurate Constraints**: Poor representation of problem constraints
 201 - **Mathematical Errors**: Errors in problem formulation or transformation
 202 - **Poor Abstractions**: Abstractions that lose important mathematical properties
 203
 204 ## Correctness-Specific Criticism Templates
 205
 206 ### For Proof Issues
 207 ```
 208 Proof Issue: [Specific mathematical proof problem]
 209 Problem: [What's wrong with the proof]
 210 Impact: [How this affects correctness]
 211 Evidence: [Specific mathematical details or missing proof elements]
 212 Priority: [Critical/High/Medium/Low]
 213 ```
 214
 215 ### For Edge Case Issues
 216 ```
 217 Edge Case Issue: [Specific edge case problem]
 218 Problem: [What edge case is missing or mishandled]
 219 Impact: [How this affects correctness]
 220 Evidence: [Specific input scenario or boundary condition]
 221 Priority: [Critical/High/Medium/Low]
 222 ```
 223
 224 ### For Assumption Issues
 225 ```
 226 Assumption Issue: [Specific assumption problem]
 227 Problem: [What's wrong with the assumption]
 228 Impact: [How this affects correctness]
 229 Evidence: [Specific mathematical justification or counterexample]
 230 Priority: [Critical/High/Medium/Low]
 231 ```
 232
 233 ## Correctness-Specific Criticism Best Practices
 234
 235 ### Do's
 236 - **Demand Formal Proofs**: Require complete mathematical proofs of correctness
 237 - **Focus on Completeness**: Ensure all cases and scenarios are covered
 238 - **Emphasize Rigor**: Insist on mathematical rigor and precision
 239 - **Verify Assumptions**: Check that all assumptions are justified
 240 - **Analyze Edge Cases**: Systematically identify and handle edge cases
 241
 242 ### Don'ts
 243 - **Accept Hand-Waving**: Don't accept informal or unproven claims
 244 - **Ignore Edge Cases**: Don't overlook boundary conditions or extreme cases
 245 - **Skip Assumptions**: Don't accept unstated or unjustified assumptions
 246 - **Compromise on Rigor**: Don't accept solutions without mathematical justification
 247 - **Mix Concerns**: Don't include implementation, performance, or system-level issues
 248
 249 ## Correctness-Specific Criticism Checklist
 250
 251 ### Proof Assessment
 252 - [ ] Is there a complete formal proof of correctness?
 253 - [ ] Are all claims mathematically justified?
 254 - [ ] Are loop invariants properly stated and proven?
 255 - [ ] Is the proof technique appropriate and rigorous?
 256 - [ ] Are all cases covered in the proof?
 257
 258 ### Edge Case Assessment
 259 - [ ] Are all edge cases identified and handled?
 260 - [ ] Are boundary conditions properly analyzed?
 261 - [ ] Are degenerate inputs considered?
 262 - [ ] Is the analysis complete for all possible inputs?
 263 - [ ] Are extreme values and limits properly handled?
 264
 265 ### Assumption Assessment
 266 - [ ] Are all assumptions explicitly stated?
 267 - [ ] Is each assumption mathematically justified?
 268 - [ ] Are the assumptions reasonable and necessary?
 269 - [ ] Do the assumptions hold for all cases?
 270 - [ ] What is the impact of each assumption on correctness?
 271
 272 ### Modeling Assessment
 273 - [ ] Is the mathematical modeling appropriate?
 274 - [ ] Are problem constraints accurately represented?
 275 - [ ] Is the problem formulation mathematically sound?
 276 - [ ] Are abstractions mathematically justified?
 277 - [ ] Is the problem transformation correct?
 278
 279 ## Correctness-Specific Evaluation Questions
 280
 281 ### For Any Algorithm
 282 1. **What is the complete formal proof of correctness?**
 283 2. **Are all edge cases and boundary conditions handled?**
 284 3. **Are all assumptions explicitly stated and justified?**
 285 4. **Are loop invariants properly stated and proven?**
 286 5. **Is algorithm termination proven?**
 287 6. **Is the mathematical modeling appropriate and accurate?**
 288 7. **Are all possible input scenarios covered?**
 289 8. **Is the analysis free from implementation concerns?**
 290 9. **Are all claims mathematically rigorous?**
 291 10. **What mathematical principles guarantee correctness?**