# All Questions

10,698 questions
Filter by
Sorted by
Tagged with
24 views

### Conjecture about ASP reductions between NP-complete problems

$ASP$-complete reductions, introduced by Ueda and Nagao, relate the hardness of computational problems in $FNP$. Basically, $ASP$-reduction is a polynomial time reduction between instances and a ...
12 views

### How is the progress on counting independent sets of various graphs?

Counting the number of solutions is harder than judging the existence of solutions. Counting independent sets of a graph is notably #P-complete, and so is of a hypergraph. Two similiar questions in ...
23 views

### Time Complexity for algorithm when input is doubled

For the following problem, I gave an answer, but I was told that my approach is not correct. The problem: Suppose you have an algorithm which for inputs of size n=1000 runs in exactly 1 second on ...
20 views

### Is the equivalence problem of Total Turing Machines decidable?

Total Turing Machines defined as Turing Machines that are guaranteed to halt. The diagonal argument used to prove the undecidability of Turing Machine equivalence doesn't seem to work here, at least ...
37 views

### NP class: decision and not decision problems [closed]

Are the problems in NP only decision problems? If yes, this means that, for example, the problem of add two numbers is NOT in P, because P is a subset of NP. And if they are only decision problems, ...
99 views

### Automatic theorem prover for first-order logic versus model checker

What's the formal difference between a model checker, and an automated theorem prover for first-order logic, i.e. something like Meson/Metis/Sledgehammer/Vampire/E? Link to a clear discussion of the ...
24 views

### Sipser: Language Regularity questions [closed]

I am currently working through the famous book "Introduction to the Theory of computation", Third edition by Michael Sipser. What I appreciate about this book is that it has many questions with ...
62 views

### Would it be possible to derive transp natively from Path, Interval and typecase?

Assume for a moment that we extended Agda with an Interval and a Path type, but not transp (which is a primitive currently). I'm ...
36 views

### Check if language is decidable [closed]

I would like to determine if the following language is decidable or not. L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}. I know that every finite ...
57 views

3k views

### Why would a TCS researcher need funding?

I was reading this. It says ... You won't find yourself as starving for funding like Pure Mathematics. (You'll still always find yourself starving for funding.)... Why do pure mathematicians need ...
108 views

### Online TCS Seminars

I want to have a list of online seminars that holds now. So far I know only about TCS+(https://sites.google.com/site/plustcs/) seminars. I would like to ask if there are other TCS seminars.
31 views

### How do you solve the following recurrence, 6T(n/3) +n^2? [closed]

I've tried to solve this question T(n) = 6T(n/3) +n^2 but i failed. Options are; a) n^3 b) logn c) nlogn d) n^2
36 views

### Scientific Journal [closed]

What are some other equivalents to a journal like SoftwareX where one can submit the methodology and codes used to solve a research problem?
97 views

2k views

### What's the relation between OOP and category theory?

What's the relation between OOP and category theory? Is there some related work on this topic one can read?
81 views

### Can the Banach-Tarski paradox be “realized” by floating-point round-off?

The Banach-Tarski paradox says that a ball in $\mathbb{R}^3$ can be partitioned into a finite number of pieces, whose rearrangement has a larger volume than the original. It occurred to me that it ...
361 views

### Formalizing the “no formula for primes” intuition

I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt: Conjecture: There is no $O(n^2)$ expected time randomized algorithm to generate $\ge n$-...
21 views

### Effect of Loop Jumps [closed]

I am studying about nested loop optimization. I came across this article. It says that just by reordering loop such that the least changing loop becomes outermost and the most changing loop becomes ...
16k views

### Funny TCS-related papers etc?

What is the funniest TCS-related published work you know? Please include only those that are intended to be funny. Works which are explicitly crafted to be intelligently humorous (rather than, say, ...
19 views

### Oracle separation between coNP and QMA implies oracle separation between NP and QMA

In [this] paper, Aaronson remarks (page 2, footnote) that: From the BBBV lower bound for quantum search , one immediately obtains an oracle $A$ such that $coNP^{A} \not\subseteq QMA^{A}$ for ...
292 views

### On the complexity of a “list” datastructure in the RAM model

I am interested in the complexity of a data-structure equipped with the following operations (similar to a list): insertion of an element at a given position within the list deletion of an element at ...
7k views

### Are there any open problems left about DFAs?

After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don'...
436 views

16 views

### Verification in the context of TLA+ compared to CSP

While reading through the paper - Composition: A way to make proofs harder, Lamport sets up the argument that it is better to reason about computational systems directly using mathematical elements ...
38 views

### Garbage collection and halting problem [closed]

I'm trying to understand a concept in theoretical computer science and I had a general (theoretical) question about carbage collection. Why isn't it possible for a garbage collector to free memory for ...
604 views

### Which formalism is best suited for automated theorem proving in set theory?

Abbreviations - FOL is first-order logic; NBG is Von Neumann–Bernays–Gödel set theory; SEP is Stanford Encyclopedia of Philosophy; HOL is higher-order logic; ATP is automated theorem proving. Context ...
277 views

### An axiom for John Major's Equality

In the the standard library of Coq, there is the axiom: Axiom JMeq_eq : forall (A:Type) (x y:A), JMeq x y -> x = y. Why isn't it provable? Can it be reduced ...
79 views

### Intuition behind the Charikar's LP formulation for densest subgraph problem

I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper. Just mentioning the LP for maximum density of a ...
99 views
+100

### Diagonalization arguments for QMA type proof systems

Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in ...
52 views

### Fastest known algorithm to enumerate k-cliques in a graph for fixed k

Is the best known algorithm for finding all $k$-cliques in a graph with $n$ nodes, for a fixed $k$, given by https://theory.stanford.edu/~virgi/combclique-ipl-g.pdf ? The time-complexity of the ...
47 views

### Query complexity for functions $f\colon\left\{0,1\right\}^n\to\left\{0,1\right\}^m$

I'm studying query complexity and I'm trying to understand Bernstein-Vazirani's problem (https://en.wikipedia.org/wiki/Bernstein%E2%80%93Vazirani_algorithm) and Simon's problem (https://en.wikipedia....