Documentation
Complexitylib
.
Circuits
.
Dependency
.
Internal
Search
return to top
source
Imports
Init
Complexitylib.Mathlib.Digraph
Complexitylib.Circuits.Dependency.Defs
Mathlib.Data.Fintype.BigOperators
Imported by
Complexity
.
Circuit
.
dependencyGraph_adj_val_lt_internal
Complexity
.
Circuit
.
dependencyGraph_isAcyclic_internal
Complexity
.
Circuit
.
dependencyGraph_edgeFinset_internal
Complexity
.
Circuit
.
dependencyGraph_edge_card_le_totalFanIn_internal
Circuit dependency graphs -- proof internals
#
source
theorem
Complexity
.
Circuit
.
dependencyGraph_adj_val_lt_internal
{
B
:
Basis
}
{
N
M
G
:
ℕ
}
[
NeZero
N
]
[
NeZero
M
]
(
c
:
Circuit
B
N
M
G
)
{
source
target
:
Fin
(
N
+
G
+
M
)
}
(
edge
:
c
.
dependencyGraph
.
Adj
source
target
)
:
↑
source
<
↑
target
source
theorem
Complexity
.
Circuit
.
dependencyGraph_isAcyclic_internal
{
B
:
Basis
}
{
N
M
G
:
ℕ
}
[
NeZero
N
]
[
NeZero
M
]
(
c
:
Circuit
B
N
M
G
)
:
c
.
dependencyGraph
.
IsAcyclic
source
theorem
Complexity
.
Circuit
.
dependencyGraph_edgeFinset_internal
{
B
:
Basis
}
{
N
M
G
:
ℕ
}
[
NeZero
N
]
[
NeZero
M
]
(
c
:
Circuit
B
N
M
G
)
:
c
.
dependencyGraph
.
edgeFinset
=
c
.
dependencyEdges
source
theorem
Complexity
.
Circuit
.
dependencyGraph_edge_card_le_totalFanIn_internal
{
B
:
Basis
}
{
N
M
G
:
ℕ
}
[
NeZero
N
]
[
NeZero
M
]
(
c
:
Circuit
B
N
M
G
)
:
c
.
dependencyGraph
.
edgeFinset
.
card
≤
c
.
totalFanIn