Complexity Techniques: Difference between revisions
Appearance
Added techniques (I know of) for derivational complexity |
Lists broken by tools |
||
| Line 5: | Line 5: | ||
=== 2009 === | === 2009 === | ||
* | ==== CaT (Winner of 2009) ==== | ||
* Triangular Matrix Interpretations | |||
* Arctic Interpretations | |||
* Rewriting Right Hand Sides | |||
* Root Labeling | |||
* Match Bounds | |||
* Modular Complexity Analysis (dc(R)=dc(R1/R2)+dc(R2/R1)) | |||
==== Matchbox ==== | |||
* Triangular Matrix Interpretations | |||
* Non-Triangular Matrix Interpretations | * Non-Triangular Matrix Interpretations | ||
* | |||
==== TCT ==== | |||
* Triangular Matrix Interpretations | |||
* Arctic Interpretations | |||
* Rewriting Right Hand Sides | |||
* Root Labeling | |||
=== 2008 === | === 2008 === | ||
==== CaT (Winner of 2008) ==== | |||
* Triangular Matrix Interpretations | * Triangular Matrix Interpretations | ||
* Arctic Interpretations | * Arctic Interpretations | ||
* Rewriting Right Hand Sides | * Rewriting Right Hand Sides | ||
* Root Labeling | |||
* Match Bounds | |||
==== TCT ==== | |||
* Triangular Matrix Interpretations | |||
* Root Labeling | * Root Labeling | ||
* Match Bounds | * Match Bounds | ||
Revision as of 12:33, 26 March 2010
This page is for listing all techniques applied by the participants of the complexity competitions.
Derivational Complexity
2009
CaT (Winner of 2009)
- Triangular Matrix Interpretations
- Arctic Interpretations
- Rewriting Right Hand Sides
- Root Labeling
- Match Bounds
- Modular Complexity Analysis (dc(R)=dc(R1/R2)+dc(R2/R1))
Matchbox
- Triangular Matrix Interpretations
- Non-Triangular Matrix Interpretations
TCT
- Triangular Matrix Interpretations
- Arctic Interpretations
- Rewriting Right Hand Sides
- Root Labeling
2008
CaT (Winner of 2008)
- Triangular Matrix Interpretations
- Arctic Interpretations
- Rewriting Right Hand Sides
- Root Labeling
- Match Bounds
TCT
- Triangular Matrix Interpretations
- Root Labeling
- Match Bounds
Runtime Complexity
2009
TBA
2008
TBA