On the P versus NP intersected with co-NP question in communication complexity

DOI10.1016/j.ipl.2005.08.003zbMath1184.68265OpenAlexW2032941175MaRDI QIDQ1044738

Stasys P. Jukna

Publication date: 18 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.08.003

zbMATH Keywords

computational complexitycommunication complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• Communication complexity
• Results on communication complexity classes
• On the distributional complexity of disjointness
• On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
• On multi-partition communication complexity
• Information Transfer under Different Sets of Protocols
• CREW PRAM<scp>s</scp> and Decision Trees
• The Probabilistic Communication Complexity of Set Intersection
• Branching Programs and Binary Decision Diagrams
• Communication Complexity

This page was built for publication: On the P versus NP intersected with co-NP question in communication complexity