Pages that link to "Item:Q1096390"
From MaRDI portal
The following pages link to Short propositional formulas represent nondeterministic computations (Q1096390):
Displaying 15 items.
- On O(Tlog T) reduction from RAM computations to satisfiability (Q758197) (← links)
- On the communication complexity of zero-knowledge proofs (Q1261016) (← links)
- Time-space tradeoffs for satisfiability (Q1567402) (← links)
- Local reduction (Q1641001) (← links)
- Sorting, linear time and the satisfiability problem (Q1817067) (← links)
- On membership comparable sets (Q1961377) (← links)
- Robust simulations and significant separations (Q2407096) (← links)
- A time lower bound for satisfiability (Q2581273) (← links)
- Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
- Local Reductions (Q3448833) (← links)
- Smoothing the Gap Between NP and ER (Q5071086) (← links)
- Power indices and easier hard problems (Q5751941) (← links)
- (Q5875468) (← links)
- Time-space tradeoffs for SAT on nonuniform machines (Q5956015) (← links)
- Rigid matrices from rectangular PCPs (Q6491304) (← links)