Data Structures and Algorithms

1908 Submissions

[6] viXra:1908.0630 [pdf] replaced on 2019-10-05 11:23:08

Determining Satisfiability of 3-Sat in Polynomial Time

Authors: Ortho Flint, Asanka Wickramasinghe, Jay Brasse, Chris Fowler
Comments: 42 Pages. Version 1 is missing a case in the theorem. Version 2 is complete.

In this paper, we provide a polynomial time (and space), algorithm that determines satisfiability of 3-SAT. The complexity analysis for the algorithm takes into account no efficiency and yet provides a low enough bound, that efficient versions are practical with respect to today's hardware. We accompany this paper with a serial version of the algorithm without non-trivial efficiencies (link: polynomial3sat.org).
Category: Data Structures and Algorithms

[5] viXra:1908.0591 [pdf] submitted on 2019-08-28 06:49:50

Computational Microscopy Imaging

Authors: George Rajna
Comments: 45 Pages.

Researchers have developed a way to enhance the imaging speed of two-photon microscopy up to five times without compromising resolution. [28] "We believe that with further advances such as OCRT, the high impact of this technology may be extended not only to additional ophthalmic diagnostics, but to imaging of pathologies in tissues accessible by endoscopes, catheters, and bronchoscopes throughout the body." [27] Working with researchers from Arizona State University, the team's new mathematical method is able to identify anomalies or bugs in the system before the car hits the road. [26]
Category: Data Structures and Algorithms

[4] viXra:1908.0562 [pdf] submitted on 2019-08-27 10:20:24

A Performance Study of RDF Stores for Linked Sensor Data

Authors: Hoan Nguyen Mau Quoc, Martin Serrano, Han Nguyen Mau, John G. Breslin, Danh Le Phuoc
Comments: 20 Pages.

The ever-increasing amount of Internet of Things (IoT) data emanating from sensor and mobile devices is creating new capabilities and unprecedented economic opportunity for individuals, organizations and states. In comparison with traditional data sources, and in combination with other useful information sources, the data generated by sensors is also providing a meaningful spatio-temporal context. This spatio-temporal correlation feature turns the sensor data become even more valuables, especially for applications and services in Smart City, Smart Health-Care, Industry 4.0, etc. However, due to the heterogeneity and diversity of these data sources, their potential benefits will not be fully achieved if there are no suitable means to support interlinking and exchanging this kind of information. This challenge can be addressed by adopting the suite of technologies developed in the Semantic Web, such as Linked Data model and SPARQL. When using these technologies, and with respect to an application scenario which requires managing and querying a vast amount of sensor data, the task of selecting a suitable RDF engine that supports spatio-temporal RDF data is crucial. In this paper, we present our empirical studies of applying an RDF store for Linked Sensor Data. We propose an evaluation methodology and metrics that allow us to assess the readiness of an RDF store. An extensive performance comparison of the system-level aspects for a number of well-known RDF engines is also given. The results obtained can help to identify the gaps and shortcomings of current RDF stores and related technologies for managing sensor data which may be useful to others in their future implementation efforts.
Category: Data Structures and Algorithms

[3] viXra:1908.0443 [pdf] submitted on 2019-08-21 21:53:33

N-SAT in P with Non-Coherent Space Factorization

Authors: F.L.B. Périat
Comments: 7 Pages.

We know since Cook that Boolean satisfiability problems with at least three literals in each clauses are in NP and are NP-complete. With proving that 3-SAT (or more) is in P, corollary proves that P = NP. In this document, we explain how to find a SAT problem solution in polynomial complexity time.
Category: Data Structures and Algorithms

[2] viXra:1908.0403 [pdf] submitted on 2019-08-20 02:18:13

Unishox Guaranteed Compression for Short Unicode Strings

Authors: Arundale Ramanathan
Comments: 15 Pages.

A new hybrid encoding method is proposed, with which short unicode strings could be compressed using context aware pre-mapped codes and delta coding resulting in surprisingly good ratios.
Category: Data Structures and Algorithms

[1] viXra:1908.0357 [pdf] replaced on 2019-09-03 07:55:02

It is Easier to Verify the Solution Than to Find it - III

Authors: Valdir Monteiro dos Santos Godoi
Comments: 23 Pages. In portuguese.

Introducing firstly the concepts of variable languages and languages with semantic and then without using them we presented original proofs of the famous P versus NP problem of Computer Science. These proofs don't implies that the NP-complete problems not belongs to P, so the P versus NP-complete problem remains open, as well as it is possible (perhaps) to solve the SAT problem in polynomial time.
Category: Data Structures and Algorithms