Questions tagged [soft-question]

The tag has no usage guidance.

6
votes
2answers
59 views

Sequence to explore the complexity of the NP problem

Let $X$ be some problem known to be in $NP$. What is the natural next step in exploring the complexity of the problem? Is it trying to prove whether it is in $P$ or try to prove it is $NP$-Hard? ...
1
vote
1answer
26 views

Looking for two-way communication/consensus/contract algorithm for use in marriage proposal

I am looking for some sort of communication or consensus algorithm with the following properties: Can be used with just two parties (and ideally doesn't collapse to a trivial case with two parties) ...
1
vote
2answers
86 views

Are there NP COMPLETE problems that are “easy” in practice?

NP COMPLETE problems are hard in the worst case (assuming $P \neq NP$). What that means is that for every polynomial $p$, sufficiently large integer $n$, and algorithm $A$, there is an instance $x$ of ...
1
vote
0answers
25 views

Practicality of Algebraic Machine Learning Methods [closed]

Last year this article was released detailing a method of high level machine learning using methods found from abstract algebra, with seemingly amazing results and claims. However, since then I have ...
1
vote
1answer
68 views

Elegant algorithm to semi-decide if two lambda calculus terms are equivalent

Given two lambda terms $t_1$ and $t_2$, it is semi-decidable if they are equivalent (i.e. can be rewritten as each other using alpha, beta, and eta conversions). An algorithm to do this is to try ...
0
votes
1answer
18 views

Examples of interesting semantics to study during a small project for a graduate Semantics course

I have been following the course Concrete Semantics with Isabelle/HOL. At some point we are given the task to verify a program/extend some semantic construction/prove some mathematical fact. I ...