All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-3
votes
0answers
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 ...
0
votes
0answers
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 ...
-3
votes
0answers
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, ...
1
vote
1answer
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 ...
-4
votes
0answers
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 ...
3
votes
0answers
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 ...
-2
votes
0answers
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 ...
2
votes
0answers
57 views

a direct polynomial reduction from 3EQU-SUM to EQU-SUM problem

Given a multiset of integers $S$, in the Equ-Sum problem we want to check whether or not $S$ can be divided into two disjoint subsets, say $X_1$, $X_2$ such that $\sum_{x_i \in X_1}x_i = \sum_{x_j \...
5
votes
1answer
221 views

Witness verifiable quantum advantage

Update: A slightly different version of this question has been answered here. As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results. ...
5
votes
1answer
263 views

Why do TCS papers have author names in alphabetical order of their surnames?

I am currently doing a Ph.D. in Theoretical Computer Science, and any research paper I encountered so far has the author's names in alphabetical order of their surnames. For example consider the most ...
-6
votes
0answers
57 views

Complexity of finding largest non-vanishing minor?

Rank of a matrix is given by $SVD$. What is the complexity of finding largest submatrix whose dimensions agree with rank? This is the largest non-vanishing minor. What is the complexity of deciding ...
-5
votes
0answers
43 views

Is there a $BPP$ like class stronger than $P$ and weaker than $BPP$?

$P/poly$ is a class of problems solvable in $P$ for every input length $n$ provided we have an advice string of length $poly(n)$ that depends only on $n$. $BPP$ is class of problems solvable with ...
1
vote
1answer
70 views

Asymptotic Approximation to Number of Knapsack Solutions

Is there an asymptotic approximation to the fraction of sets satisfying a knapsack feasibility constraint? More precisely, imagine I have a large number $n$ of items with bounded weights $X_1,...,X_n ...
25
votes
7answers
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 ...
3
votes
1answer
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.
-3
votes
0answers
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
-2
votes
0answers
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?
3
votes
1answer
97 views

What arithmetical theorems can plain $\lambda \Pi$ reason about?

I've read that System F cannot state or prove theorems of the First Order Theory of Arithmetic. I assume this is because we lack dependent types, so we cannot explicitly express $\forall n:\mathbb{N}....
39
votes
3answers
2k views

Is there a backup/replacement for the Complexity Zoo?

This is a non-technical question, but certainly relevant for the TCS community. If considered inappropriate, feel free to close. The Complexity Zoo webpage (http://qwiki.stanford.edu/index.php/...
-3
votes
0answers
27 views

Minimum vertex cut with component sum less than a constant threshold [closed]

Given an undirected graph with $n$ vertices. Each vertex $i$ is associated with a weight $w_i$. Find a minimum set of vertices that can be removed from the graph such the each connected component in ...
1
vote
1answer
44 views

Name of (and solution to) this generalization of linear assignment

I would like to know if the following problem is known and has any efficient solution. Given an $n\times n$ score matrix $S$. Find the best $a$ elements, in terms of their sum of scores, such that no ...
1
vote
0answers
30 views

Given a program specification, S, what can be said about the size and efficiency of programs that exactly satsify S, with respect to the size of S?

Suppose we are given a program specification, $S$, and we want to reason about programs $P$ that satisfy $S$. One might like to think that if the specification is 'simple', the the program should be '...
1
vote
1answer
33 views

kmeans++ for arbitrary metric spaces and general potential function

I was reading this popular paper "k-means++: The Advantages of Careful Seeding". It appeared in SODA 2007. Since this technique is the most popular clustering technique, I am hoping that my question ...
1
vote
2answers
46 views

Disjoint subsets problem complexity

Is the decision problem below NP-complete? Given sets $S_1, ... , S_n$, as well as bounds $b_1, ... , b_n$, is it possible to pick pairwise disjoint subsets $U_1, ... , U_n$ such that $U_i \subset ...
7
votes
3answers
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?
2
votes
1answer
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 ...
9
votes
1answer
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$-...
-1
votes
0answers
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 ...
80
votes
42answers
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, ...
0
votes
0answers
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 [6], one immediately obtains an oracle $A$ such that $coNP^{A} \not\subseteq QMA^{A}$ for ...
6
votes
2answers
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 ...
62
votes
10answers
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'...
5
votes
1answer
436 views

Factoring with LLL when the form of the factors is given

Given a degree $2k$ reducible polynomial $$f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$$ with $$\text{gcd}(a_{2k},\dots,a_0)=1$$ that is known to be of the form $f_1(x)f_2(x)$ with $\text{deg}\big(...
-2
votes
0answers
33 views

Smallest Bicubic Graph without a Hamilton Path [closed]

I found a lot literature in the net about graphs without hamiltonian cycles but I can't find the Smallest Bicubic Graph without Hamilton Path I also don't care about planarity or connectivity. ...
2
votes
1answer
84 views

Additive versus multiplicative accuracy

I am trying to understand the difference between $\epsilon$-additive and $\epsilon$-multiplicative algorithms. The way I understand this definition is as follows. An $\epsilon$-additive algorithm is ...
0
votes
0answers
29 views

Different version of approximation complexity and algorithm for densest-k-subgraph problem

In the densest-k-subgraph problem, we are given a graph $G =(V,E)$ and $k$, and we are asked to find a set $S \in V$ of vertices to maximize the number of edges in the induced graph of $S$, i.e. $|Ind[...
-1
votes
0answers
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 ...
-4
votes
0answers
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 ...
2
votes
2answers
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 ...
6
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
3
votes
0answers
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 ...
0
votes
0answers
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....
-2
votes
0answers
19 views

Runtime trial division [closed]

I am studying primality testing. It is claimed that trial division takes O(n) operations. For large primes it is therefore infeasible. It is claimed that trial division is not polynomial. But is not O(...
3
votes
0answers
26 views

Is Rackoff's bound on the length of shortest covering executions in VAS still the best known one?

In 1976–1977, Rackoff proved in The covering and boundedness problems for vector addition systems that the length of a shortest covering sequence in a VAS is bounded by $2^{(3n)^n} = 2^{2^{(\log_2 3)n\...
0
votes
0answers
16 views

ANN for 2D-Coordinate Classification

I have a dataframe of spatial data where X- and Y-Coordinates and the belonging of these coordinates to territorial units are given. Now I would like to train an ANN to classify coordinates to the ...
-4
votes
0answers
45 views

On the classes $E$, $DTIME$ and $NTIME$? [closed]

For every $c>0$ is there a $c'$ such that $DTIME(n^c)^E\subseteq DTIME(2^{n^{c'}})$ hold and vice versa for every $d'>0$ is there a $d$ such that $DTIME(2^{n^{d'}})\subseteq DTIME(n^d)^E$ hold? ...

15 30 50 per page
1
2 3 4 5
214