3
votes
0answers
13 views

Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers. Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence ...
3
votes
1answer
54 views

Why was there a need for Martin-Löf to create intuitionistic type theory?

I've been reading up on Intuitionistic Type Theory (ITT) and it does make sense. But what I'm struggling to understand is "why" was it created in the first place? Intuitionistic Logic (IL) and ...
-1
votes
0answers
28 views

An algorithm to produce, not necessarily efficiently, another algorithm that efficiently solves the Rubik cube

How complex is the task to formulate an algorithm that produces, not necessarily efficiently, another algorithm to efficiently solves the Rubik cube? Has it been attempted before? What is the latest ...
1
vote
0answers
25 views

Software that generates and solves a Lasserre hierarchy

Suppose L is a linear program that is a relaxation of some 0/1 integer linear program ILP. There is a systematic way to construct SDP relaxations of ILP that are tighter than L by using a Lasserre ...
2
votes
0answers
43 views

Techniques introduced to log-rank conjecture

What have been some of techniques (like discrepancy, arithmetic combinatorics) that have been introduced to shed light on Log-rank conjecture which roughly states that deterministic communication ...
0
votes
0answers
22 views

Maximum set cover of graph with r density requirement

I am trying to implement a satisfactory solution to a variation of maximum coverage problem. A set of people is in relation to a set of channels by liking them. Each channel has a unique relationship ...
5
votes
0answers
115 views

Partition of a set of integers into subsets with prescribed sums

I saw this problem: A non increasing sequence of positive integers $m_1,m_2,..., m_k$ is said to be n-realizable if the set $I_n=\{1,2,..., n\}$ can be partitioned into $k$ mutually disjoint subsets ...
2
votes
0answers
57 views

Decidability of CFG ambiguity

I have been trying to show the following language is undecidable. $L = \{ (\langle G \rangle , n ): G$ is a context-free grammar with an ambiguous string of length $\le n \}$. I think it is ...
-3
votes
0answers
21 views

Quantum multi valued decision diagrams [migrated]

I recently came across the paper "QMDD: A Decision Diagram Structure for Reversible and Quantum Circuits" by Thornton and Miller. It deals with a way of compactly representing transformation matrix ...
0
votes
0answers
73 views

Proof of Non Deterministic Space Hierarchy Theorem [on hold]

I am trying to prove the Non Deterministc Space Hierarchy Theorem, which says: If $f$ and $g$ are two functions such that $f=o(g)$ where $g$ is fully space constructible and $g(n) \ge \text {log }n$, ...
-2
votes
0answers
51 views

A bucket must exist before anything can be put into it. What does not have to? [on hold]

Going over the Wikipedia for Bucket (computing), I have noticed under the section 'Features of a bucket' it mentions: A bucket must exist before anything can be put into it. Why was it so ...
24
votes
6answers
1k views

Problems with big open complexity gaps

This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves. To be more ...
-3
votes
0answers
20 views

multiobjective optimization is easier with fewer objectives, right?

i guess that optimization on nonconvex problems can usually reach better results when there's fewer criteria in the objective function. for example, in a given amount of search time, ten equally ...
-5
votes
0answers
27 views

I dont understand the reduction of 3DM to Partition Problem [on hold]

I am real need for understanding the reduction from 3DM to Partition problem. I am following the textbook by Gary and Johnson. I am not understanding the argument which says that, If its 3DM will have ...
3
votes
0answers
41 views

Looking for easy applications of fractional cascading

I want to give a couple of talks on fractional cascading, one of which will focus on applications. I'm looking for applications that make use of the full version of fractional cascading, not just the ...
-2
votes
1answer
97 views

Why can't Horn-SAT be solved in Log-space? [on hold]

A simple algorithm for Horn-SAT (in CNF) is the following: Given: A Horn formula $\phi$ in CNF. Find a unit clause (a clause with one literal) $C_i$. $~$Set the variable $x_j$ appearing in $C_i$ to ...
2
votes
1answer
115 views

Efficient recalculation of the maximum flow when edge capacities are reduced

Assume that we have a (directed) graph $G(V \cup \{s, t\}, E)$ and an (integer) capacity function $c : E \mapsto \mathbb{N}$. Let $f : E \mapsto \mathbb{N}$ be a maximum $s-t$ flow on this graph. ...
-2
votes
0answers
43 views

Karatsuba's algorithm smart step analysis [on hold]

I have a problem that I want to solve. I really tried but it does not budge. If the input is of size n for Karatsuba's algorithm We have three steps in Karatsuba's algorithm: 1) Recursively compute ...
1
vote
1answer
88 views

Good algorithms to solve ATSP

What are some good neighborhood-based local search algorithms or strategies to solve the Asymmetric TSP ? I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations), but I think ...
1
vote
1answer
68 views

Minimum order of partite in a bipartite graph

I want to create a bipartite graph where the first partite $U$ contains $L$ vertices with degree $k$ and the second partite $V$ contains $N$ other vertices with degree $a$. I need to find the minimum ...
4
votes
1answer
83 views

Upper bounds on higher order eigenvalues of regular graphs

Suppose $G$ is an undirected $d$-regular $n$-vertex graph for some constant $d$. Let $\lambda_k$ be the $k$-th largest eigenvalue of the normalized laplacian $L$ of $G$ (defined as $I - \frac{1}{d} A$ ...
0
votes
1answer
60 views

Many-one reduction from inequality problem to equality problem

Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is: ...
-6
votes
0answers
61 views

All NP-Problems have pseudopolynominaltime algorithms [closed]

Knapsack is weakly Np-complete. Every problem in NP is in polynominal time reduceable to an Knapsack instance. Knapsack has a pseudopolynominaltime algorithmvia dynamic programming. So there is a ...
0
votes
0answers
68 views

Finding Contextual Nodes in a Knowledge Graph

I'm currently participating in developing a knowledge graph that uses ConceptNet and a few others as its data sources. It uses the same architecture as ConceptNet namely it is stored as a Hypergraph ...
3
votes
0answers
69 views

Comparing the Kolmogorov complexity of theories - Part 2

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
29
votes
2answers
497 views

Is there an oracle such that SAT is not infinitely often in sub-exponential time?

Define $io$-$SUBEXP$ to be the class of languages $L$ such that there is a language $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ and for infinitely many $n$, $L$ and $L'$ agree on all ...
1
vote
1answer
48 views

Finite state transducer with infinitary outputs or without emphasis on acceptance?

1) Is there a notion of (deterministic) finite state transducer (FST) that allows the possibility of producing an infinite stream of output symbols? In other words, one where the transduction ...
-1
votes
0answers
30 views

Pseudoflow in oriented graph

I have a hard time solving the following problem: We have an oriented graph with positive integer capacities. We are also given for each vertex v the minimal sum of flows from edges in in-direction ...
1
vote
1answer
158 views

Has this formulation of pursuit evasion been researched? Similar to Helicopter Cops and Robbers Game

There are pursuers and evaders in the vertices of a directed graph G with one component. Each vertex must have atleast one outgoing edge (can be a loop). At each time t: The evaders must move ...
7
votes
1answer
204 views

Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics). I am particularly ...
0
votes
0answers
33 views

Detect highly weighted but also densely inter-connected subnetworks

In a connected / undirected / node weighted (with both positive and negative weights) network, there are many papers studied about the 'Maximum weight connected subgraph' problem. But are there any ...
-4
votes
0answers
54 views

non-Hamiltonian cubic planar graphs [on hold]

What is the current state of knowledge about whether a polynomial deterministic algorithm has to be able to output every Hamiltonian circuit in every instance of a cubic planar graph $G$ in order to ...
1
vote
0answers
67 views

Complexity of Approximating Vandermonde Determinant

Given an $n\times n$ Vandermonde integer matrix with structured integers (such as arithmetic or geometric progression). Is complexity of approximately computing Vandermonde determinant upto ...
-2
votes
0answers
55 views

$FNP \subset FPSPACE$? [closed]

it is clear, that $NP \subseteq PSPACE$ holds and that it is unknown if the strict inclusion holds. how is it if one looks at the corresponding functional complexity classes? Does $FNP \subset ...
5
votes
1answer
235 views

How would a theory of computation course that culminated in lambda-calculus as “the” model of computation, instead of Turing machines, look like?

Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics: Finite automata and regular languages Pushdown automata and context-free languages Turing ...
4
votes
0answers
69 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

I already posted this question here but I didn't receive an answer, so I'm posting it here as well :) Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as ...
-1
votes
0answers
32 views

Reduction n-dimensional Problem to n-1-dimensional Problem

I've proved that $$ a^Tx=b, x_0,...,x_n \geq0 \mbox{ and integer} $$ where ($a^T$ is a vector of $n$ numbers, x integer), which is np-complete, is aquivalent to a different system: $$ c^Ty\leq e $$ ...
-1
votes
0answers
42 views

How to interpret this question? [closed]

I think I'll be able to figure this out on my own once I understand what they're asking me, but I'm finding this homework question a bit ambiguous. Here it is word for word: "Construct a regular ...
-3
votes
1answer
77 views

Algorithm to determine if given algorithm runs in polynomial time [duplicate]

In general, the undecidability of the halting problem prohibits the general determination of an algorithm's complexity. However, I can see no reason why the halting problem prohibits one from deciding ...
-1
votes
0answers
48 views

What type of automaton was Bombe?

Rafael already asked "Was bombe machine turing complete?", and we can easily agree that 'Bombe' wasn't Turing equivalent since it wasn't capable of solving any other problem aside cracking Enigma ...
4
votes
1answer
149 views

possible bridge between group growth theory and complexity theory?

RJ Lipton conjectures a link between group growth theory and complexity theory. Group growth theory has undergone rapid advance in the last decade and has many surface similarities/ parallels with ...
-4
votes
0answers
31 views

Using Azuma's inequality to upperbound the size of the largest clique in a random graph [closed]

Let $G_n,\frac{1}{2}$ be a random graph. I would like to show that for some constants $c,t$, it holds that: $Pr[G\,contains\,a\,clique\,of\,size\;c\cdot log(n)]<\frac{1}{t}$ I saw an example of ...
-3
votes
1answer
75 views

Using Yao's minimax principle [closed]

Consider the basic problem in which the input is an array A of n bits, and we need to output some index i with A[i]=1 (we can read a single bit each time). Can you give me an example using Yao's ...
-3
votes
0answers
31 views

A fast algorithm for a simple multi-objective minimization? [closed]

I have a set of n (arbitrary) integer numbers S which I want to partition into k subsets S_i each of size n/k (you can assume that k divides n). Let A be the arithmetic mean of elements of the set S. ...
-3
votes
1answer
55 views

When an algorithm can be easily parallelized, should I pursue research and improvements for a serialized model? [closed]

This is a question about the usefulness of serial vs parallel algorithms. I am currently working on a research topic where I am developing a certain algorithm. This algorithm can easily be ...
2
votes
0answers
41 views

Parameterized Complexity of Minimum Type Selection

Consider the following problem that I call »Minimum Type Selection«: Input: $k$ sets of bit vectors, each of length $n$ and a number $l$. Question: Is it possible to pick exactly one bit vector from ...
-3
votes
0answers
45 views

Using Fermat's sieving in multiplication [closed]

I am working on Integer Factorization problem, and I came to idea of applying Fermat's sieving improvement in multiplication. Let it be $N$ the value we want to factor, such that $$N = ab$$ Now I ...
3
votes
1answer
64 views

Clarification for argument in proof of search in N^1/3 queries with hidden variables/non-collapsing measurements

Let $N=2^n$. In Aaronson's Quantum Computing and Hidden Variables (1) and the recent follow up by Aaronson, Bouland, Fitzsimons, and Lee The space "just above" BQP (2), we consider models of ...
4
votes
1answer
71 views

Have these coloring games been solved?

In the paper "On the complexity of some coloring games", Bodlaender gives some open questions about the complexity of deciding if player 1 or 2 has a winning strategy in some graph coloring games. ...
-2
votes
1answer
45 views

What is the applications of kmp algorithm? [closed]

KMP algorithm works best when there is/are self matching(s) of pattern string that we want to search for. Usually it doesn't happen unless pattern is long enough. So where is the KMP application in ...

15 30 50 per page