Theoretical Computer Science Stack Exchange
Theoretical Computer Science Stack Exchange

Most Popular

more tags
1500 questions
18
votes
0 answers

In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?

Decision Problem Input: An $m$ by $n$ Boolean matrix $M$. Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left corner entry == lower-right corner entry == 1? That…
Michael Wehar
  • 5,127
  • 1
  • 24
  • 54
18
votes
1 answer

The quad-edge data structure (Delaunay/Voronoi)

2 questions for the computational geometers or algebraists: I am just beginning to dive into computational geometry and I am loving it =) I am attempting to read the famous article by Guibas and Stolfi called "Primitives for the manipulation of…
bigmonachus
  • 283
  • 2
  • 5
18
votes
7 answers

In the neutral zone between polynomial and sub-exponential

What are examples of problems that are known to be sub-exponential, but are known to be non-polynomial, or are not known to be polynomial? EDIT. Here is what I mean by sub-exponential (apologies for leaving this open). A function…
Dominic van der Zypen
  • 905
  • 6
  • 16
18
votes
0 answers

Perfect matching of monotone Boolean function with null Euler characteristic

For a set $V = \{0,\ldots,k\}$ of variables, let $\mathbf{G}_V$ be the undirected graph with set of vertices $\{S \subseteq V\}$ and set of edges $\{\{S,S'\} \mid S \subseteq S' \text{ and }|S'| = |S|+1\}$, in other words the underlying undirected…
M.Monet
  • 1,429
  • 7
  • 19
18
votes
3 answers

How to talk about theory

I realize this might be a contentious question, but this seemed like the right place to ask. Please redirect me if not. The background is that I am a "practitioner" (PhD student, I don't study CS theory) but I have a reasonable foundation in…
user219923
  • 283
  • 1
  • 6
18
votes
1 answer

Algorithm whose running time depends on P vs. NP

Is there a known, explicit example of an algorithm with the property such that if $P\neq NP$ then this algorithm doesn't run in polynomial time and if $P=NP$ then it does run in polynomial time?
user2925716
  • 317
  • 1
  • 7
18
votes
4 answers

How are imperative languages more different from each other than functional languages?

I'm reading Simon Peyton Jones's The Implementation of Functional Programming Languages and there's one statement that surprised me a little bit (on page 39): To a much greater extent than is the case for imperative languages, functional…
Jason
  • 397
  • 1
  • 8
18
votes
2 answers

Is an NP-hardness proof of an NP-hard problem considered a contribution?

I am solving a problem that is claimed to be NP-hard elsewhere, say in the paper [XYZ]. The NP-hardness provided in [XYZ] is complicated and uses advanced techniques. After some research and work, I succeeded to give a simple and clear proof of the…
zdm
  • 325
  • 1
  • 10
18
votes
3 answers

Type-based memory safety without manual memory manage or runtime garbage collection?

Let's say we wanted a typeful, pure functional programming language, like Haskell or Idris, that is aimed at systems programming without garbage collection and has no runtime (or at least not more than the C and Rust "runtimes"). Something that can…
analogyschema
  • 283
  • 1
  • 6
18
votes
2 answers

Implicit vs explicit subtyping

This page asserts that many languages do not use implicit subtyping (structural equivalence), prefering explicit/declared subtyping (declaration equivalence) I've mostly used programming languages which uses explicit subtyping. What are the…
Frankie Ribery
  • 291
  • 1
  • 5
18
votes
2 answers

Is it possible to encrypt a CNF?

Is it possible to convert a CNF $\mathcal C$ into another CNF $\Psi(\mathcal C)$ such that The function $\Psi$ can be computed in polynomial time from some secret random parameter $r$. $\Psi(\mathcal C)$ has a solution if and only if $\mathcal C$…
domotorp
  • 13,931
  • 37
  • 93
18
votes
2 answers

"Almost sorting" integers in linear time

I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but arithmetic operations on them are assumed to take…
a3nm
  • 9,269
  • 27
  • 86
18
votes
1 answer

What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

Background It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$. It is even known that the separation holds relative to a random oracle. Informally, one may interpret this to mean that there are many oracles for which…
Michael Wehar
  • 5,127
  • 1
  • 24
  • 54
18
votes
1 answer

Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?

Many theorems and "paradoxes" - Cantor's diagonalization, undecidability of hatling, undeciability of Kolmogorov complexity, Gödel Incompleteness, Chaitin Incompleteness, Russell's paradox, etc. - all have essentially the same proof by…
Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
18
votes
3 answers

Quantified Boolean Formulas with logarithmic alternations

I'm studying a problem which is hard for the class of quantified boolean formulas with a logarithmic number of alternations of the quantifiers. A problem in this class would look like: $\forall (x_1, x_2, \ldots x_{a_1}) \exists (x_{{a_1}+1}, \ldots…
isaacg
  • 806
  • 6
  • 14
1 2 3
…
99 100